[Leetcode] Binary Tree Traversal

Posted on | In , , |

Solutions: https://www.youtube.com/watch?v=as1f6PJmbAE&t=50s

Level Order Traversal (Breadth First Traversal)

102. Binary Tree Level Order Traversal

Leetcode: https://leetcode.com/problems/binary-tree-level-order-traversal/description/

Solution

[1] My solution: Use two Queues to seperately store values on different depth of the tree

[2] DFS solution: construct [[], [], []] first, then use dep to track depth of the tree; Fill in the empty [] when traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// DFS Solution
class Solution {
 public void dfs(List<List<Integer>> ans,TreeNode root,int dep) {
     if(root==null) {
         return;
     }
     if(ans.size()<=dep) {
         ans.add(new ArrayList());
     }
     ans.get(dep).add(root.val);
     dfs(ans,root.left,dep+1);
     dfs(ans,root.right,dep+1);
 }
 public List<List<Integer>> levelOrder(TreeNode root) {
     List<List<Integer> > ans = new ArrayList();
     dfs(ans,root,0);
     return ans;
 }
}

103. Binary Tree Zigzag Level Order Traversal

Leetcode: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

[Solution] Use level % 2 == 0 to decide how to insert value into sublists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    private void dfs(TreeNode root, int level) {
        if (root == null) return;
        if (res.size() <= level) res.add(new ArrayList());

        if (level % 2 == 0) res.get(level).add(root.val);
        else res.get(level).add(0,root.val); // change direction of insertion

        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}

107. Level Order travesal II, bottom up

Leetcode: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public int height = 0;

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return result;
        dfs(root, 0);
        return result;
    }


    public void dfs(TreeNode root, int dep) {

        if (dep >= result.size()) { // [] not exist yet
            result.add(0, new ArrayList<Integer>());
        }
        result.get(result.size() - dep - 1).add(root.val);
        if (root.left != null) dfs(root.left, dep + 1);
        if (root.right != null) dfs(root.right, dep + 1);
    }
}

199. Binary Tree Right Side View

Leetcode: https://leetcode.com/problems/binary-tree-right-side-view/description/

[dfs solution]

The result list should return all the rightmost nodes in each level of the tree. Since it should recognize ‘level’, we should set up a variable to keep track of the level. Once the res.length == level, we append the root.val and forward to the next level.

This solutions uses right level oriented preorder traversal. Will check right child node first, if it’s null, return and go to left child.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList();
        dfs(root, res, 0);
        return res;
    }

    private void dfs(TreeNode root, List<Integer> res, int depth) {
        if (root == null) return;
        if (res.size() == depth) {
            res.add(root.val);
        }
        dfs(root.right, res, depth + 1); // IMPORTANT TO GO RIGHT FIRST
        dfs(root.left, res, depth + 1);
    }
}

Raised question about dfs(root.right, res, depth++) at StackOverflow: https://stackoverflow.com/questions/53018302/whats-the-difference-between-depth-1-and-depth-in-this-dfs-recursion-functi
[bfs solution]

Depth First Traversal

Introduction: https://www.youtube.com/watch?v=cIoGuSCU14A

100. Same Tree(easy)

[Recursive solution] Just need to check if left tree == right tree

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        else if (p != null && q != null && p.val == q.val) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return false;
    }
}

[Iterative Solution] Use a stack to keep comparing left child tree and right child tree.

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
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
      Stack s = new Stack<TreeNode[]>();
      TreeNode[] temp = new TreeNode[2];

      if (p == null && q == null) return true;
      temp[0] = p;
      temp[1] = q;

      s.push(temp);

      while (!s.isEmpty()) {
          temp = new TreeNode[2];
          temp = (TreeNode[]) s.pop();
          TreeNode l = temp[0];
          TreeNode r = temp[1];

          if (l == null && r == null) continue;
          else if (l != null && r != null && l.val == r.val) {
              temp = new TreeNode[2];
              temp[0] = l.left;
              temp[1] = r.left;
              s.push(temp);
              temp = new TreeNode[2];
              temp[0] = l.right;
              temp[1] = r.right;
              s.push(temp);
          } else return false;
      }
      return true;
    }
}

101. Symmetric Tree

[Solution] Construct a new function that allows two parameters, left, and right, compare left.right and right.left tree.

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

    private boolean helper(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        else if (left != null && right != null && left.val == right.val) {
            return helper(left.right, right.left) && helper(left.left, right.right);
        }else return false;
    }
}

110. Balanced Binary Tree

[Solution] TBA

Pre-order Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Leetcode: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

[Solution-recursion]

Key: There is not duplicates in the tree. Thus, the root will be the first element in the pre-order array, and you can find the index of the root in the in-order array. The subarray on the left of the root in the in-order array will be the left sub-tree, vice versa.

1
2
3
4
5
6
7
8
9
10
11
12
13
      1
     / \
    2   8
   / \  /
  5   6 7

Preorder: [1,2,5,6,8,7]
           ^ |---| |--|
        root left right

Inorder: [5,2,6,1,7,8]
          |---| ^ |--|
          left root right
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
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length > 0) {
            TreeNode root = new TreeNode(preorder[0]);

            if (preorder.length > 1) {
                List<Integer> tempin  = new ArrayList<Integer>();

                for (int num: inorder) {
                    tempin.add(num);
                }

                int rootIn = tempin.indexOf(preorder[0]);

                int[] leftPre = Arrays.copyOfRange(preorder, 1, rootIn+1);
                int[] rightPre = Arrays.copyOfRange(preorder, rootIn+1, preorder.length);
                int[] leftIn = Arrays.copyOfRange(inorder, 0, rootIn);
                int[] rightIn = Arrays.copyOfRange(inorder, rootIn + 1, inorder.length);

                root.left = buildTree(leftPre, leftIn);
                root.right = buildTree(rightPre,rightIn);
            }
            return root;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    if not preorder or not inorder:
        return
    def build(pre, inr):
        if len(pre) == len(inr) == 0:
            return
        if len(pre) == 1:
            return TreeNode(pre[0])
        
        i = inr.index(pre[0])
        head = TreeNode(inr[i])
        
        head.left = build(pre[1: len(inr[:i]) + 1], inr[:i])
        head.right = build(pre[len(inr[:i]) + 1:], inr[i+1:])
        return head
    return build(preorder, inorder)

An elegant python solution:

1
2
3
4
5
6
7
def buildTree(self, preorder, inorder):
    if inorder:
        ind = inorder.index(preorder.pop(0))
        root = TreeNode(inorder[ind])
        root.left = self.buildTree(preorder, inorder[0:ind])
        root.right = self.buildTree(preorder, inorder[ind+1:])
        return root

114. Flatten Binary Tree to LinkedList

Leetcode: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

[Solution] Use a Dummy Node prev to keep track of nodes in each level.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    TreeNode prev = null; // Dummy Node
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

297. Serialize and Deserialize Binary Tree

Leetcode: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Pretty good Video: https://www.youtube.com/watch?v=suj1ro8TIVY

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
from collections import deque
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        def rserialize(root, s):
            if not root:
                s += 'None,'
            else:
                s += str(root.val) + ','
                s = rserialize(root.left, s)
                s = rserialize(root.right, s)
            return s
        return rserialize(root, '')

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == 'None,':
                return
        data = deque(data.split(','))
        
        def rdeserialize(data):
            nxt = data.popleft()
            if nxt == 'None':
                return
            node = TreeNode(int(nxt))
            node.left = rdeserialize(data)
            node.right = rdeserialize(data)
            return node

        return rdeserialize(data)

1110. Delete Nodes And Return Forest

Leetcode: https://leetcode.com/problems/delete-nodes-and-return-forest/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def delNodes(self, root, to_delete):
    to_delete = set(to_delete)
    added = set()
    res = []
    def dfs(parent, node, direction):
        if not node:
            return
        if node.val not in to_delete:
            if parent not in added:
                res.append(node)
            added.add(node)
        elif parent:
            if direction == "left":
                parent.left = None
            else:
                parent.right = None
        dfs(node, node.left, "left")
        dfs(node, node.right, "right")
    dfs(None, root, "left")
    return res

In-order Traversal

Iterative In-order Traversal

Introduction: https://www.youtube.com/watch?v=VsxLHGUqAKs

  1. Create an empty stack S
  2. Initialize current node as root
  3. Push the current node to S and set current = current.left until current == null
  4. if current is null and stack is not empty
    a. pop the top item from stack
    b. print the popped item, set current = popped_item.right
    c. go to step 3
  5. If current == null and stack is empty finish iteration
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void inorderTraverse(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode current = root;

        while(true) {
            while (current != null) {
                s.push(current);
                current = current.left;
            }

            if (!s.isEmpty() && current == null) {
                TreeNode temp = s.pop();
                System.out.println(temp.val); // visit popped TreeNode
                current = temp.right;
            }

            if (current == null && s.isEmpty()) break;
        }
    }

Visit left first, then check if current node has a right child, if so, visit right child.

1
2
3
4
5
6
7
8
9
10
11
12
def inorderTraversal(self, root: TreeNode) -> List[int]:
    stack = []
    res = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res

106. Construct Binary Tree from Inorder and Postorder Traversal

Solution same as 105.
Leetcode: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

94.Inorder Traversal

Leetcode: https://leetcode.com/problems/binary-tree-inorder-traversal/description/

Solution: Generic Class Unit

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
class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      Deque<Guide> path = new ArrayDeque<>();

      path.addFirst(new Guide(0, root));

      while(!path.isEmpty()) {
          Guide current = path.removeFirst();
          if (current.node == null) continue; // defensive...

          if (current.ope == 1) {
              result.add(current.node.val);
          } else {
              path.addFirst(new Guide(0, current.node.right));
              path.addFirst(new Guide(1, current.node));
              path.addFirst(new Guide(0, current.node.left));
          }
      }
      return result;
  }

  private class Guide {
      int ope;
      TreeNode node;
      public Guide(int ope, TreeNode node) {
          this.ope = ope;
          this.node = node;
      }
  }
}

Post-order Traversal

226. Invert Binary Tree(easy)

Leetcode: https://leetcode.com/problems/invert-binary-tree/description/

Solution: just reverse the left child and right child

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

110. Balanced Binary Tree

Leetcode: https://leetcode.com/problems/balanced-binary-tree/description/

Solution: Test if the abs(left - right) > 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Fastest solution
class Solution {
  boolean flag = true;

  public boolean isBalanced(TreeNode root) {
      dfs(root);
      return flag;
  }

  private int dfs(TreeNode node) {
      if(node == null) return 0;
      int l = dfs(node.left);
      int r = dfs(node.right);

      if(Math.abs(l - r) > 1) flag = false;
      return Math.max(l, r) + 1;
  }
}

145. Postorder Traversal

Leetcode: https://leetcode.com/problems/binary-tree-postorder-traversal/description/

Solution: Use generic class Unit, set operation

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
class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<Unit> s = new Stack<Unit>();
    s.push( new Unit(0, root));

    while(!s.isEmpty()) {
        Unit current = s.pop();
        if (current.node == null) continue;

        if (current.operation == 1) {
            result.add(current.node.val);
        } else {
            s.push(new Unit(1, current.node));
            if(current.node.right != null) s.push(new Unit(0, current.node.right));
            if(current.node.left != null) s.push(new Unit(0, current.node.left));
        }
    }
    return result;
  }

  private class Unit {
    int operation;
    TreeNode node;
    Unit(int o, TreeNode c) {
        this.operation = o;
        this.node = c;
    }
  }
}

297. Serialize and Deserialize Binary Tree (Hard)

Leetcode: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

[Solution]

  1. Use pre-order traversal to push nodes in an array
  2. Use pre-order traversal to construct the tree back from string
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
/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
const serialize = (root) => {
    let arr = new Array();
    
    dfs(root, arr);
    return arr.join(",");
};

const dfs = (root, arr) => {
    
    if (root === null) {
        arr.push("X");
        return;
    }
    
    arr.push(root.val);
    
    dfs(root.left, arr);
    dfs(root.right, arr);
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
const deserialize = (str) => {
    let data = str.split(",");
    let root = construct(data);
    
    return root;
};

const construct = (data) => {
    let root = new TreeNode(data.shift());
    
    if (root.val === "X") {
        return null;
    }
    
    root.left = construct(data);
    root.right = construct(data);
    
    return root;
};