🌲 Blog 10: Advanced Tree Traversals & Encoding

[Dev Cookies]

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;
    }
}

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;
    }
}

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;
    }
}

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;
    }
}

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;
    }
}

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;
    }
}

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.

Continue reading...

 

Join 𝕋𝕄𝕋 on Telegram
Channel PREVIEW: