Binary Tree

Posted on | In

A binary tree is a tree where each node has at most two children. Suppose the depth of a binary tree is k, then it has at most 2^k children.
A complete binary tree is a binary tree where every level (except the last) is completely filled, and all nodes at the last level are as far left as possible.
A full binary tree is a complete binary tree where every node other than the leaves has two children.

This post is about some classic problems relating to the binary tree. Most of the problems can be solved using DFS.

I. Traversal

i. Pre-order traversal

Leetcode: 144. Binary Tree Preorder Traversal.

Recursive solution:

1
2
3
4
5
6
void preorder(TreeNode node) {
    if (node == null) return;
    // handle the current node
    preorder(node.left);
    preorder(node.right);
}

Itervative solution:

1
2
3
4
5
6
7
8
9
10
void preorder(TreeNode root) {
    Deque<TreeNode> stack = new Deque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // handle the current node;
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

ii. In-order traversal

Leetcode: 94. Binary Tree Inorder Traversal.

Recursive solution:

1
2
3
4
5
6
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    // handle the current node
    inorder(node.right);
}

Itervative solution:

1
2
3
4
5
6
7
8
class StackNode {
    TreeNode node;
    boolean hasProcessed;
    StackNode(TreeNode node) {
        this.node = node;
        this.hasProcessed = false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void inorder(TreeNode root) {
    Deque<StackNode> stack = new Deque<>();
    stack.push(new StackNode(root));
    while (!stack.isEmpty()) {
        StackNode node = stack.pop();
        if (node.hasProcessed) {
            // handle the current node
        } else {
            if (node.right != null) stack.push(new StackNode(node.right));
            stack.push(node);
            if (node.left != null) stack.push(new StackNode(node.left));
            node.hasProcessed = true;
        }
    }
}

Or use a set to record the nodes which have been processed (as shown in iii).

iii. Post-order traversal

Leetcode: 145. Binary Tree Postorder Traversal.

Recursive solution:

1
2
3
4
5
6
void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    // handle the current node
}

Itervative solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void postorder(TreeNode root) {
    Deque<TreeNode> stack = new Deque<>();
    stack.push(new StackNode(root));
    Set<TreeNode> mark = new HashSet<>();
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (mark.contains(node)) {
            // handle the current node
        } else {
            stack.push(node);
            if (node.right != null) stack.push(new StackNode(node.right));
            if (node.left != null) stack.push(new StackNode(node.left));
            mark.add(node);
        }
    }
}

iv. Construct a binary tree using pre-order and in-order (or post-order and in-order)

For pre-order traversal, the first element is the root of the tree (similar for post-order traversal), and follows the nodes of the left subtree, and then the nodes of the right subtree. How do we know which nodes belong the left subtree? The answer is in the in-order traversal, the nodes on the left side of the root belong to the left subtree, and the nodes on the right side belong to the right subtree. The next thing is to construct the left subtree and the right one, divide and conquer, and this is how to construct a binary tree.
In a word, we use the pre-order/post-order traversal to local the root of subtree, and use in-order traversal to find the nodes in the left subtree and in the right subtree.

Leetcode: 105. Construct Binary Tree from Preorder and Inorder Traversal and 106. Construct Binary Tree from Inorder and Postorder Traversal .

v. Symmetric Tree

101. Symmetric Tree: check if a binary tree is a mirror of itself.

The idea is to traverse the left subtree and right subtree in an opposite way. Note that simply using in-order traversal to generate an array and then checking if it is symmetric is not enough. Check a counter example below.

1
2
3
4
5
    1
   / \
  2   4
 /   /
4   2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return dfs(root.left, root.right);
}

private boolean dfs(TreeNode lTree, TreeNode rTree) {
    if (lTree == null && rTree == null) {
        return true;
    }
    if (lTree == null && rTree != null || lTree != null && rTree == null || lTree.val != rTree.val) {
        return false;
    }

    return dfs(lTree.left, rTree.right) && dfs(lTree.right, rTree.left);
}

vi. Level order traversal

Leetcode: 102. Binary Tree Level Order Traversal.

The solution is to use BFS to explore tree nodes by level.

1
2
3
4
5
6
7
8
9
10
11
12
queue.add(root);
int count = 1;
while (!queue.isEmpty()) {
    int childCount = 0;
    while (count > 0) {
        Node node = queue.poll();
        if (node.left != null) { queue.add(node.left); childCount++; }
        if (node.right != null) { queue.add(node.right); childCount++; }
        count--;
    }
    count = childCount;
}

vii. Morris traversal

It is a different kind of traversal without recursion and without stack. Its space complexity is O(1).

II. Serialize & Deserialize

Leetcode: 297. Serialize and Deserialize Binary Tree.

The key is to find a way to serialize a binary tree to a string. One obvious way is to put the result of pre-order (or post-order) traversal and in-order traversal together, but this will take up space twice as the tree’s size.

One solution is provided by LeetCode OJ. It traverses the tree in level order and prints each node including the children which are null (so that each node can find their parents when deserialized), but the last nulls can be removed. The implementation is easy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) { sb.append("null,"); continue; }
        sb.append(node.val).append(",");
        queue.add(node.left);
        queue.add(node.right);
    }
    // remove extra null and ,
}

TreeNode deserialize(String sequence) {
    TreeNode root = null;
    if ("".equals(sequence)) return root;

    String[] array = sequence.split(",");
    root = new TreeNode(Integer.valueOf(array[0]));
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int i = 1;
    while (!queue.isEmpty() && i < array.length) {
        TreeNode node = queue.poll();
        if (!"null".equals(array[i])) {
            node.left = new TreeNode(Integer.valueOf(array[i]));
            queue.add(node.left); 
        }
        i++;
        if (!"null".equals(array[i])) {
            node.right = new TreeNode(Integer.valueOf(array[i]));
            queue.add(node.right);
        }
        i++;
    }
}

The other solution is to use in-order traversal, but to introduce extra marks to indicate the level of each node, e.g. (((5)2)1(3(4))) represents the tree as follows: there are 3 pairs of parentheses around node 5, so it is at level 3, and for the same reason, the level of node 2 is 2, and because node 5 is on the left side of node 2, node 5 is the left child of node 2.

1
2
3
4
5
    1
   / \
  2   3
 /     \
5       4

The part of serialization is super easy, but the part of deserialization is much more difficult.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
String serialize(TreeNode node) {
    if (node == null) return "";
    return "(" + serialize(node.left) + node.val + serialize(node.right) + ")";
}

TreeNode deserialize(String sequence) {
    if ("".equals(sequence)) return null;

    int pCounter = 0; // counter for parentheses
    Deque<StackNode> stack = new Deque<>();
    int i = 0, num = 0, sign = 1;
    boolean handleNum = false;
    while (i < sequence.length()) {
        char ch = sequence.charAt(i);
        if (ch == '-') {
            sign = -1;
            i++;
            continue;
        }
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch - '0');
            i++;
            handleNum = true;
            continue;
        }

        if (handleNum) {
            processNewNode(new TreeNode(num * sign), pCounter, stack);
            num = 0;
            sign = -1;
            handleNum = false;
        }
        if (ch == '(') {
            pCounter++;
        } else if (ch == ')') {
            pCounter--;
        }
        i++;
    }
    if (handleNum) {
        processNewNode(new TreeNode(num), stack);
    }
    return stack.get(0).node;
}

void processNewNode(TreeNode tNode, int level, Deque<StackNode> stack) {
    // alway pop out the nodes of the left subtree from the stack
    // the stack is left with the most right path
    if (!stack.isEmpty()) {
        StackNode topNode = stack.pop();
        // topNode is in the left subtree of tNode
        if (topNode.level > level) {
            while (!stack.isEmpty() && topNode.level - 1 > level) {
                topNode = stack.pop();
            }
            tNode.left = topNode;
        } 
        if (!stack.isEmpty()) {}
            topNode = stack.peek();
            // tNode is the right child of topNode
            if (topNode.level + 1 == level) {
                topNode.node.right = topNode;
            }
        }
    }
    stack.push(new StackNode(tNode, level));
}

class StackNode {
    TreeNode node;
    int level;
    StackNode(Tree node, int level) {
        this.node = node;
        this.level = level;
    }
}

III. Lowest Common Ancestor

236. Lowest Common Ancestor of a Binary Tree: find the lowest common ancestor (LCA) of two given nodes p and q in a binary tree.

If the binary tree has links connecting each node to its parent, we can apply the solution of two pointers to this problem. But here we need to figure out something else.

The idea is to let the ancestors of p or q be aware that p or q is in the subtree. We can use the return value to pass what we need upwards. As the image below shows, move p or q upwards until the lcs is found, and then move the lcs upwards.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode lcs(TreeNode node) {
    // The amazing thing about this implementation is that
    // the function returns null when the node is null,
    // so for each node that is not the ancestor of p or q, the function will return null.
    // This simplifies the implementation, 
    // otherwise it will take some efforts to distinguish the lcs from other nodes.
    if (node == null || node == q || node == p) {
        return node;
    }
    TreeNode left = lcs(node.left);
    TreeNode right = lcs(node.right);
    if (left != null && right != null) return node;
    if (left != null) return left;
    return right;
}

IV. More

i. Flattern a binary tree

114. Flatten Binary Tree to Linked List: flattern a binary tree to a linked list in-place.

The solution is divide and conquer. For each subtree, flattern its left subtree, link its right child to the last node of the left subtree, and make its left child as its right child; and then flattern its right subtree, and return its last node.

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode flattern(TreeNode node) {
    if (node == null || node.left == null && node.right == null) return node;
    TreeNode right = node.right;
    TreeNode lLast = flattern(node.left);
    if (lLast != null) {
        lLast.right = right;
        node.right = node.left;
        node.left = null;
    }
    TreeNode rLast = flattern(right);
    return rLast != null ? rLast : lLast;
}

ii. Sum

129. Sum Root to Leaf Numbers: given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number; find the total sum of all root-to-leaf numbers.

The solution is pre-order traversal: generate a number when encounter a leaf node.

1
2
3
4
5
6
int sum(TreeNode node, int num) {
    if (node == null) return 0;
    int tmp = num * 10 + node.val;
    if (node.left == null && node.right == null) return tmp;
    return sum(node.left, tmp) + sum(node.right, tmp);
}

References

1 Morris Traversal