DEV Community

Dev Cookies
Dev Cookies

Posted on

🌲 Blog 10: Advanced Tree Traversals & Encoding

We’ve covered height, DFS/BFS, diameter, DP, LCA, views, serialization, and BST patterns.
This last blog focuses on advanced traversals & encoding/decoding problems that often appear in interviews.

🔍 Why Advanced Traversals?

Sometimes normal inorder/preorder/postorder isn’t enough.
We need:

  • Space-efficient traversals (Morris traversal).
  • Serialization/Deserialization (encode tree → string, rebuild tree).
  • Iterative traversals with stack/queue patterns.

✅ Classic Problems

1. Serialize & Deserialize Binary Tree (LeetCode 297)

Encode tree into a string, then rebuild.

class Codec { public String serialize(TreeNode root) { if (root == null) return "null,"; return root.val + "," + serialize(root.left) + serialize(root.right); } public TreeNode deserialize(String data) { Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(","))); return build(nodes); } private TreeNode build(Queue<String> nodes) { String val = nodes.poll(); if (val.equals("null")) return null; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = build(nodes); node.right = build(nodes); return node; } }
Enter fullscreen mode Exit fullscreen mode

Pattern: Preorder traversal with null markers.

2. Serialize & Deserialize BST (LeetCode 449)

Can optimize by not storing nulls, since BST property allows reconstruction.

class Codec { public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); preorder(root, sb); return sb.toString(); } private void preorder(TreeNode node, StringBuilder sb) { if (node == null) return; sb.append(node.val).append(","); preorder(node.left, sb); preorder(node.right, sb); } public TreeNode deserialize(String data) { if (data.isEmpty()) return null; Queue<Integer> queue = new LinkedList<>(); for (String s : data.split(",")) { if (!s.isEmpty()) queue.offer(Integer.parseInt(s)); } return build(queue, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode build(Queue<Integer> queue, int min, int max) { if (queue.isEmpty()) return null; int val = queue.peek(); if (val < min || val > max) return null; queue.poll(); TreeNode node = new TreeNode(val); node.left = build(queue, min, val); node.right = build(queue, val, max); return node; } }
Enter fullscreen mode Exit fullscreen mode

Pattern: Preorder + BST constraints.

3. Morris Traversal (Inorder without Recursion/Stack)

Space-optimized traversal: O(1) space, O(n) time.

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); TreeNode curr = root, pre; while (curr != null) { if (curr.left == null) { res.add(curr.val); curr = curr.right; } else { pre = curr.left; while (pre.right != null && pre.right != curr) { pre = pre.right; } if (pre.right == null) { pre.right = curr; curr = curr.left; } else { pre.right = null; res.add(curr.val); curr = curr.right; } } } return res; } }
Enter fullscreen mode Exit fullscreen mode

Pattern: Threaded tree traversal.

4. Binary Tree Iterative Traversals

Sometimes recursion isn’t allowed — stack/queue helps.

Inorder Iterative 

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; } }
Enter fullscreen mode Exit fullscreen mode

Preorder Iterative 

class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val); if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return res; } }
Enter fullscreen mode Exit fullscreen mode

Postorder Iterative 

class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> res = new LinkedList<>(); if (root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.addFirst(node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } return res; } }
Enter fullscreen mode Exit fullscreen mode

🎯 Quick Pattern Checklist

  • Serialize/Deserialize → Preorder with nulls (general tree) / BST constraints (BST only).
  • Morris Traversal → O(1) space inorder traversal.
  • Iterative Traversals → Replace recursion with stack/queue.
  • Threaded Trees → Modify pointers temporarily for traversal.

🔥 Final Takeaway

Across this series, we’ve seen all major tree patterns:

  • Height/recursion
  • Traversals (DFS, BFS)
  • Diameter & DP on trees
  • Views (top, bottom, left, right, boundary, vertical, diagonal)
  • LCA patterns
  • Serialization
  • BST patterns
  • Advanced traversals

👉 Once you can recognize which pattern a problem falls into, solving it becomes a matter of applying the right template.

Top comments (0)