# Tree

[**Cheat Sheet**](https://medium.freecodecamp.org/tree-traversals-explained-theyre-like-a-class-of-lazy-students-trying-to-cheat-on-their-exam-b46563211427)

[**Explanation**](https://www.tutorialspoint.com/data_structures_algorithms/tree_traversal.htm)

[**Iterative**](https://www.hackerearth.com/practice/notes/iterative-tree-traversals/)<br>

### **Binary Tree Traversal**

#### [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)

```python
# ITERATION
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        if not root:
            return res
        stack.append(root)
        while stack:
            curt = stack.pop()
            res.append(curt.val)
            if curt.right:
                stack.append(curt.right)
            if curt.left:
                stack.append(curt.left)
        return res

# RECURSION
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if root == None:
            return
        res.append(root.val)
        self.helper(root.left, res)
        self.helper(root.right, res)
```

#### [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

```python
# ITERATION
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        if not root:
            return res
        self.addLeft(root, stack)
        while stack:
            curt = stack.pop()
            res.append(curt.val)
            self.addLeft(curt.right, stack)
        return res
    
    def addLeft(self, curt, stack):
        while curt:
            stack.append(curt)
            curt = curt.left

# RECURSION
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res) -> None:
        if root == None:
            return
        self.helper(root.left, res)
        res.append(root.val)   
        self.helper(root.right, res)
```

#### [145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)

```python
# ITERATION
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        if not root:
            return res
        stack.append(root)
        while stack:
            curt = stack.pop()
            res.append(curt.val)
            if curt.left:
                stack.append(curt.left)
            if curt.right:
                stack.append(curt.right)
        res.reverse()
        return res
        
# RECURSION
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if root == None:
            return
        self.helper(root.left, res)
        self.helper(root.right, res)
        res.append(root.val)  
```

[**226. Invert Binary Tree**](https://leetcode.com/problems/invert-binary-tree/)

Swap left node with right node.

```python
    def invertTree(self, root: TreeNode) -> TreeNode:
        self.helper(root)
        return root
    
    def helper(self, root) :
        if not root:
            return
        temp = root.right
        root.right = root.left
        root.left = temp
        self.helper(root.left)
        self.helper(root.right)
```

#### [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

Top - down

```python
    res = 0
    def maxDepth(self, root: TreeNode) -> int:
        self.helper(root, 1)
        return self.res
    
    
    def helper(self, curt, depth):
        if not curt:
            return
        self.res = max(self.res, depth)
        self.helper(curt.left, depth + 1)
        self.helper(curt.right, depth + 1)
```

Bottom - up

```python
    def maxDepth(self, root: TreeNode) -> int:
        return self.helper(root, 1)
    
    def helper(self, curt, depth):
        if not curt:
            return 0
        L = self.helper(curt.left, depth + 1)
        R = self.helper(curt.right, depth + 1)
        return max(max(L, R), depth)
```

#### [559. Maximum Depth of N-ary Tree](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/)

```java
public int maxDepth(Node root) {
    return helper(root);
}

private int helper(Node curt) {
    if (curt == null) return 0;
    int max = 0;
    for (Node child : curt.children) {
        max = Math.max(max, helper(child));
    }
    return max + 1;
}
```

#### [257. Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/)

{% tabs %}
{% tab title="Java" %}

```java
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) return res;
        dfs(root, new StringBuilder(), res);
        return res;
    }
    
    private void dfs(TreeNode root, StringBuilder sb, List<String> res) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            sb.append(root.val);
            res.add(sb.toString());
            return;
        }
        sb.append(root.val).append("->");
        int len = sb.length();
        dfs(root.left, sb, res);
        sb.setLength(len);
        dfs(root.right, sb, res);
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []
        self.helper(root, "", result)
        return result
    
    def helper(self, root, curt, res):
        if not root:
            return
        if not root.left and not root.right:
            curt += str(root.val)
            res.append(curt)
            return 
        curt += str(root.val) + "->"
        self.helper(root.left, curt, res)
        self.helper(root.right, curt, res)
        
```

{% endtab %}
{% endtabs %}

#### [100. Same Tree](https://leetcode.com/problems/same-tree/)

#### [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)

#### [572. Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)

```java
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
    }
```

#### [110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)

把左边和右边的结果放到一个variable存一下，看看是不是哪边=-1或者两边的差大约1

```python
    res = True
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        self.helper(root)
        return self.res
    
    def helper(self, curr):
        if not curr:
            return 0
        L = self.helper(curr.left)
        R = self.helper(curr.right)
        self.res = (abs(L - R) <= 1) and self.res
        return max(L, R) + 1
```

#### [236. Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)

Bottom-up and detect the node is on both L and R or just one side?

{% tabs %}
{% tab title="Java" %}

```java
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode L = lowestCommonAncestor(root.left, p, q);
        TreeNode R = lowestCommonAncestor(root.right, p, q);
        if (L != null && R != null) {
            return root;
        } else if (L == null && R != null) {
            return R;
        } else if (L != null && R == null) {
            return L;
        } 
        return null;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if root == p or root == q:
            return root
        L = self.lowestCommonAncestor(root.left, p, q)
        R = self.lowestCommonAncestor(root.right, p, q)
        if L and R:
            return root
        if L and not R:
            return L
        if not L and R:
            return R
        return None
```

{% endtab %}
{% endtabs %}

#### [112. Path Sum](https://leetcode.com/problems/path-sum/)

Traverse to see if a leaf node value equals sum, deduct current node val on each node.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == sum;
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
```

{% endtab %}

{% tab title="Python" %}

```python
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return sum == root.val
        sum -= root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
```

{% endtab %}
{% endtabs %}

#### [113. Path Sum II](https://leetcode.com/problems/path-sum-ii/)

Traverse down the tree,  add new node value to the list. **Deep copy current list on each level**.

{% tabs %}
{% tab title="Java" %}

```java
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        helper(root, sum, new ArrayList<>(), result);
        return result;
    }
    
    private void helper(TreeNode root,
                        int sum,
                        List<Integer> curtList, 
                        List<List<Integer>> res) {
        if (root == null) return;
        curtList.add(root.val);
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                res.add(new ArrayList<>(curtList));
            }
            return;
        }
        helper(root.left, sum - root.val, new ArrayList<>(curtList), res);
        helper(root.right, sum - root.val, new ArrayList<>(curtList), res);
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        self.helper(root, [], res, sum)
        return res
        
    def helper(self, root, curt, res, sum):
        if not root:
            return
        curt.append(root.val)
        if not root.left and not root.right and sum == root.val:
            res.append(copy.deepcopy(curt))
        self.helper(root.left, curt, res, sum - root.val)
        self.helper(root.right, curt, res, sum - root.val)
        curt.pop()
```

{% endtab %}

{% tab title="Python (deep copy on each level)" %}

```python
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        self.helper(root, [], res, sum)
        return res
        
    def helper(self, root, curt, res, sum):
        if not root:
            return
        curt.append(root.val)
        sum -= root.val
        if not root.left and not root.right:
            if sum == 0:
                res.append(copy.deepcopy(curt) )
            return
        self.helper(root.left, copy.deepcopy(curt), res, sum)
        self.helper(root.right, copy.deepcopy(curt), res, sum)
```

{% endtab %}
{% endtabs %}

This version of backtracking. No need to make a deep-copy of the current list.

```java
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        helper(root, sum, new ArrayList<>(), result);
        return result;
    }
    
    private void helper(TreeNode root,
                        int sum,
                        List<Integer> curtList, 
                        List<List<Integer>> res) {
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                curtList.add(root.val);
                res.add(new ArrayList<>(curtList));
                curtList.remove(curtList.size() - 1);
            }
            return;
        }
        curtList.add(root.val);
        if (root.left != null) helper(root.left, sum - root.val, curtList, res);
        if (root.right != null) helper(root.right, sum - root.val, curtList, res);
        curtList.remove(curtList.size() - 1);
    }
```

#### [437. Path Sum III](https://leetcode.com/problems/path-sum-iii/)

This question asks all Path Sum starting any node to any node, but only go downwards. It can be easily achieved by using the previous method + start fresh traversal at each node.

*T: O(n^2)*

```java
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int helper(TreeNode root, int sum) {
        if (root == null) return 0;
        int count = 0;
        if (sum == root.val) count += 1;
        count += helper(root.left, sum - root.val);
        count += helper(root.right, sum - root.val);
        return count;
    }
```

This can also achieved by using PrefixSum. Maintain a current sum and count of the prefix sum numbers in a HashMap ( key : the prefix sum, value : how many ways get to this prefix sum). Add the node value to the prefix sum. `curtSum - target` indicates that theres is a range sum in the path equals to target.  Put curtSum in the map. **When backtracking, reduce a count by 1 as it shouldn't count the current node anymore.**&#x20;

This method is very similar with [LC560](https://leetcode.com/problems/subarray-sum-equals-k).

{% tabs %}
{% tab title="Java" %}

```java
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return helper(root, sum, 0, map);
    }
    
    private int helper(TreeNode root, 
                       int target, 
                       int curtSum, 
                       Map<Integer, Integer> map) {
        if (root == null) return 0;
        curtSum += root.val;
        int count = map.getOrDefault(curtSum - target, 0);
        map.put(curtSum, map.getOrDefault(curtSum, 0) + 1);
        count += helper(root.left, target, curtSum, map) + helper(root.right, target, curtSum, map);
        map.put(curtSum, map.get(curtSum) - 1);
        return count;
    }
```

{% endtab %}

{% tab title="Java (top-down)" %}

```java
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    map.put(0, 1);
    helper(root, sum, 0);
    return res;
}

private void helper(TreeNode root, int k, int sum) {
    if (root == null) return;
    sum += root.val;
    if (map.containsKey(sum - k)) {
        res += map.get(sum - k);
    }
    map.put(sum, map.getOrDefault(sum, 0) + 1);
    helper(root.left, k, sum);
    helper(root.right, k, sum);
    map.put(sum, map.getOrDefault(sum, 0) - 1);
}
```

{% endtab %}
{% endtabs %}

#### [298. Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/)

{% tabs %}
{% tab title="Java" %}

```java
    int max = Integer.MIN_VALUE;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root, 0 , root.val);
        return max;
    }

    private void helper(TreeNode root, int curtLength, int target) {
        if (root == null) return;
        curtLength = (root.val == target) ? curtLength + 1 : 1;
        max = Math.max(max, curtLength);
    
        helper(root.left, curtLength, root.val + 1);
        helper(root.right, curtLength, root.val + 1);
    }
```

{% endtab %}

{% tab title="Java (Top-Down with Parent)" %}

```java
    int max = 1;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root, null, 1);
        return max;
    }
    
    private void helper(TreeNode root, TreeNode parent, int seq) {
        if (root == null) {
            return;
        }
        if (parent != null && root.val == parent.val + 1) {
            max = Math.max(max, seq + 1);
            helper(root.left, root, seq + 1);
            helper(root.right, root, seq + 1);
        } else {
            helper(root.left, root, 1);
            helper(root.right, root, 1);
        }
    }
```

{% endtab %}

{% tab title="Java (Bottom-Up)" %}

```java
    int max = 1;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        helper(root);
        return max;
    }
    
    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, null);
        }
        Result L = helper(root.left);
        Result R = helper(root.right);
        int seq = 1;
        if (L.node != null && L.node.val == root.val + 1) {
            seq = Math.max(seq, L.seq + 1);
        }
        if (R.node != null && R.node.val == root.val + 1) {
            seq = Math.max(seq, R.seq + 1);
        }
        max = Math.max(max, seq);
        return new Result(seq, root);
    }
    
    class Result {
        int seq;
        TreeNode node;
        Result(int seq, TreeNode node) {
            this.seq = seq;
            this.node = node;
        }
    }
```

{% endtab %}

{% tab title="Java (Bottom-up no Global)" %}

```java
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return helper(root).max;
    }
    
    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, 0, null);
        }
        Result L = helper(root.left);
        Result R = helper(root.right);
        int seq = 1;
        if (L.node != null && L.node.val == root.val + 1) {
            seq = Math.max(seq, L.seq + 1);
        }
        if (R.node != null && R.node.val == root.val + 1) {
            seq = Math.max(seq, R.seq + 1);
        }
        int max = Math.max(Math.max(L.max, R.max), seq);
        return new Result(seq, max, root);
    }
    
    class Result {
        int seq;
        int max;
        TreeNode node;
        Result(int seq, int max, TreeNode node) {
            this.seq = seq;
            this.node = node;
            this.max = max;
        }
    }
```

{% endtab %}
{% endtabs %}

#### [549. Binary Tree Longest Consecutive Sequence II](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/)

```java
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return helper(root).max;
    }
    
    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, 0, 0, null);
        }
        Result L = helper(root.left);
        Result R = helper(root.right);
        int Linc = 1, Ldec = 1, Rinc = 1, Rdec = 1;
        if (L.node != null) {
            if (L.node.val == root.val + 1) {
                Ldec = L.dec + 1;
            } else if (L.node.val == root.val - 1) {
                Linc = L.inc + 1;
            }
        }
        if (R.node != null) {
            if (R.node.val == root.val + 1) {
                Rdec = R.dec + 1;
            } else if (R.node.val == root.val - 1) {
                Rinc = R.inc + 1;
            }
        }
        int max = 1;
        int maxInc = Math.max(Linc, Rinc), maxDec = Math.max(Ldec, Rdec);
        max = Math.max(Math.max(maxInc, maxDec), max);
        max = Math.max(Math.max(Linc + Rdec - 1, Rinc + Ldec - 1), max);
        max = Math.max(Math.max(L.max, R.max), max);
        return new Result(maxInc, maxDec, max, root);
    }
    
    class Result {
        int inc, dec;
        int max;
        TreeNode node;
        Result(int inc, int dec, int max, TreeNode node) {
            this.inc = inc;
            this.dec = dec;
            this.max = max;
            this.node = node;
        }
    }
```

#### [124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)

{% tabs %}
{% tab title="Java" %}

```java
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(helper(root.left), 0);
        int right = Math.max(helper(root.right), 0);
        max = Math.max(max, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
class Result:
    def __init__(self, maxSum, singlePathSum):
        self.maxSum = maxSum
        self.singlePathSum = singlePathSum
    
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        return self.helper(root).maxSum
    
    def helper(self, root):
        if not root:
            return Result(-sys.maxsize, 0)
        L = self.helper(root.left)
        R = self.helper(root.right)
        lInt = max(L.singlePathSum, 0)
        rInt = max(R.singlePathSum, 0)
        return Result(max(lInt + rInt + root.val, max(L.maxSum, R.maxSum)), 
                      max(lInt, rInt) + root.val)
```

{% endtab %}

{% tab title="Python (global max)" %}

```python
    res = -sys.maxsize
    def maxPathSum(self, root: TreeNode) -> int:
        self.helper(root)
        return self.res
    
    def helper(self, root):
        if not root:
            return 0
        L = max(self.helper(root.left), 0)
        R = max(self.helper(root.right), 0)
        self.res = max(self.res, L + R + root.val)
        return max(L, R) + root.val
```

{% endtab %}
{% endtabs %}

#### [543. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)

Bottom-up and return the longest path from bottom, which is `Math.max(L, R) + 1`. In addition, each node can be a potential root of the best result, therefore update the global max at each node by  max = `Math.max(L + R, max)`

*T: O(n) S: O(n)*

Top - down

```java
    int max = 0;
    Map<TreeNode, Integer> map;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        map = new HashMap<>();
        helper(root);
        return max;
    }
    
    private void helper(TreeNode root) {
        if (root == null) return;
        max = Math.max(max, maxPath(root.left) + maxPath(root.right));
        helper(root.left);
        helper(root.right);
    }
    
    private int maxPath(TreeNode root) {
        if (root == null) return 0;
        if (map.containsKey(root)) return map.get(root);
        int res = Math.max(maxPath(root.left), maxPath(root.right)) + 1;
        map.put(root, res);
        return res;
    }
```

Bottom - up

{% tabs %}
{% tab title="Java" %}

```java
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        helper(root);
        return max;
    }
    
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int L = helper(root.left);
        int R = helper(root.right);
        max = Math.max(L + R, max);
        return Math.max(L, R) + 1;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
class Result:
    def __init__(self, maxLen, singleLen):
        self.maxLen = maxLen
        self.singleLen = singleLen
            
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        return self.helper(root).maxLen
        
    def helper(self, root):
        if not root:
            return Result(0, 0)
        L = self.helper(root.left)
        R = self.helper(root.right)
        curtMax = max(L.singleLen + R.singleLen, max(L.maxLen, R.maxLen))
        return Result(curtMax, max(L.singleLen, R.singleLen) + 1)
```

{% endtab %}

{% tab title="Python (global max)" %}

```python
    res = 0
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.helper(root)
        return self.res
        
    def helper(self, root):
        if not root:
            return 0
        L = self.helper(root.left)
        R = self.helper(root.right)
        self.res = max(L + R, self.res)
        return max(L, R) + 1
```

{% endtab %}
{% endtabs %}

[**117. Populating Next Right Pointers in Each Node II**](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)

Level order traversal and connect next nodes

*T: O(n)  S: O(n)*

```java
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node prev = queue.poll();
            if (prev.left != null) queue.offer(prev.left);
            if (prev.right != null) queue.offer(prev.right);
            for (int i = 1; i < size; i++) {
                Node curt = queue.poll();
                if (curt.left != null) queue.offer(curt.left);
                if (curt.right != null) queue.offer(curt.right);
                prev.next = curt;
                prev = curt;
            }
        }
        return root;
    }
```

Iterative connectio&#x6E;**:**&#x20;

* `head` to represent the first node of the next level
* `prev` to represent the previous node (similar as linkedlist)
* `curt` to represent the current node (similar as linkedlist)

Use curt to traverse in each level, and connect the children. If the left/right child exist, and prev is not null, then use prev to connect. Otherwise if prev is null, it means that node is head.&#x20;

T: O(n)  S: O(1)

```java
    public Node connect(Node root) {
        if (root == null) return null;
        Node head = root;
        Node prev = null;
        Node curt = null;
        while (head != null) {
            curt = head;
            prev = null;
            head = null;
            while (curt != null) {
                if (curt.left != null) {
                    if (prev != null) {
                        prev.next = curt.left;
                    } else {
                        head = curt.left;
                    }
                    prev = curt.left;
                }
                if (curt.right != null) {
                    if (prev != null) {
                        prev.next = curt.right;
                    } else {
                        head = curt.right;
                    }
                    prev = curt.right;
                }
                curt = curt.next;
            }
        }
        return root;
    }
```

#### [662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/)

Top-down traverse. Map the tree node position to an array, which means the left node is `pos * 2` and right node pos is `pos * 2 + 1`. In preorder traversal, you will encounter the left most node, hence record the `pos` of the node in the Hashmap.&#x20;

For the rest of nodes, the width will be right `pos - left + 1`. Update the global `max` on each node.

```java
    int max = 1;
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        helper(root, map, 0, 0);
        return max;
    }
    
    private void helper(TreeNode root, 
                        Map<Integer, Integer> map, 
                        int depth,
                        int pos) {
        if (root == null) return;
        map.putIfAbsent(depth, pos);
        max = Math.max(max, pos - map.get(depth) + 1);
        helper(root.left, map, depth + 1, pos * 2);
        helper(root.right, map, depth + 1, pos * 2 + 1);
    }
```

**Traversal Time Complexity:**

For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges.

Since a Binary Tree is also a Graph, the same applies here. The complexity of each of these Depth-first traversals is O(n+m).

Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes.

The complexity then becomes O(n + n-1), which is O(n).<br>

#### [987. Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)

Build coordinates of each node, sort by y and node val.&#x20;

```java
    int minX = 0;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, List<Node>> map = new HashMap<>();
        dfs(root, 0, 0, map);
        for (int key : map.keySet()) {
            Collections.sort(map.get(key), new Comparator<Node>(){
                public int compare(Node a, Node b) {
                    if (a.y == b.y) return a.node.val - b.node.val;
                    return a.y - b.y;
                }
            });
            int xIndex = map.get(key).get(0).x - minX;
            while (res.size() <= xIndex) res.add(new ArrayList<>());
            for (Node n : map.get(key)) {
                res.get(xIndex).add(n.node.val);
            }
        }
        return res;
    }
    
    private void dfs(TreeNode root, int x, int y, Map<Integer, List<Node>> map) {
        if (root == null) return;
        minX = Math.min(minX, x);
        map.putIfAbsent(x, new ArrayList<>());
        Node node = new Node(root, x, y);
        map.get(x).add(node);
        dfs(root.left, x - 1, y + 1, map);
        dfs(root.right, x + 1, y + 1, map);
    }
    
    class Node {
        int x, y;
        TreeNode node;
        Node(TreeNode n, int x, int y) {
            this.node = n;
            this.x = x;
            this.y = y;
        }
    }
```

#### **Delete a Node in Binary Tree**

1. **Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.**
2. **Replace the deepest rightmost node’s data with node to be deleted.**
3. **Then delete the deepest rightmost node.**

#### **Binary Search Tree**

* [**Search & Insert**](https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/)
* [**Delete**](https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/)
  * **Four Key factors:**
    * **IS NOT IN A TREE: do nothing**
    * **IS A LEAF: just remove it**
    * **HAS ONLY ONE CHILD: Copy the child to the node and delete the child**
    * **HAS TWO CHILDREN: Find inorder successor of the node. Copy contents of the** [**inorder successor**](https://www.techiedelight.com/find-inorder-predecessor-given-key-bst/) **to the node and delete the inorder successor. Note that** [**inorder predecessor**](https://www.techiedelight.com/find-inorder-predecessor-given-key-bst/) **can also be used.**
* **450. Delete Node in a BST**
* [**Morris Traversal**](http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html)

**250. Count Univalue Subtrees**

**用Boolean来记录左边和右边的结果，看是不是univalue subtrees，如果左边右边都是的话，Count++，返回True。如果左边右边都是，但是两边有Null或者值不等于Root Value，返回False**

&#x20;      `if (node == null) return true;`

&#x20;       `boolean left = helper(node.left);`

&#x20;       `boolean right = helper(node.right);`

&#x20;       `if (left && right) {`

&#x20;           `if ((node.left != null && node.left.val != node.val) || (node.right != null && node.right.val != node.val)) {`

&#x20;               `return false;`

&#x20;           `}`

&#x20;           `count++;`

&#x20;           `return true;`

&#x20;       `}`

&#x20;       `return false;`

**366. Find Leaves of Binary Tree**

**用Level来记录从下往上的层数，最下面Null是-1，往上是0，这样的话可以用res.get(level).add(curt.val) 来往结果里加值。如果结果里Array数小于level + 1说明没有那个Array，要建个新的**

&#x20;       `if (curt == null) return -1;`

&#x20;       `int level = 1 + Math.max(helper(curt.left, res), helper(curt.right, res));`

&#x20;       `if (res.size() < level + 1) {`

&#x20;           `res.add(new ArrayList<>());`

&#x20;       `}`

&#x20;       `res.get(level).add(curt.val);`

&#x20;       `return level;`

**337. House Robber III**

**有很多重复运算，因为要先算所有include 自己的情况，然后exclude自己的情况，取Max。**[**解**](https://leetcode.com/problems/house-robber-iii/discuss/79344/Easy-to-understand\(java\))

* **Improvement:** [**用Hashmap可以记录每个点的max**](https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem)
* **Improvement：** [**用Array**](https://leetcode.com/problems/house-robber-iii/discuss/79363/Easy-understanding-solution-with-dfs)

**107. Binary Tree Level Order Traversal II**

* **用Queue的话，和I不一样的地方就是这个在上面插入List。result.add(0,list);**
* **用Recursion，**

`if(level >= list.size()) {`

&#x20;               `list.add(0, new LinkedList<Integer>());`

&#x20;           `}`

&#x20;           `levelMaker(list, root.left, level+1);`

&#x20;           `levelMaker(list, root.right, level+1);`

&#x20;           `list.get(list.size()-level-1).add(root.val);`

**199. Binary Tree Right Side View**

* Queue是用i == qSize - 1判断最右边
* Recursion用currDepth == result.size()判断最右边，然后每下一层depth + 1

```java
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }
    
    private void dfs(TreeNode root, int depth, List<Integer> res ) {
        if (root == null) return;
        if (depth == res.size()) {
            res.add(root.val);
        }
        dfs(root.right, depth + 1, res);
        dfs(root.left, depth + 1, res);
    }
```

[**572.Subtree of Another Tree**](https://leetcode.com/problems/subtree-of-another-tree/)

#### [1120. Maximum Average Subtree](https://leetcode.com/problems/maximum-average-subtree/)

Bottom up to get the answer.

```java
double res = Double.MIN_VALUE;
public double maximumAverageSubtree(TreeNode root) {
    helper(root);
    return res;
}

private int[] helper(TreeNode root) {
    if (root == null) {
        return new int[2];
    }
    int[] L = helper(root.left);
    int[] R = helper(root.right);
    int sum = L[0] + R[0] + root.val;
    int count = L[1] + R[1] + 1;
    res = Math.max(res, (double)sum / (double)count);
    return new int[]{sum, count};
}
```

[**114.Flatten Binary Tree to Linked List**](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)

[**108.Convert Sorted Array to Binary Search Tree**](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)

* * **Use left, right, mid**
    * **If left > right -> return null**
    * **If left == right -> return nums\[left]**
    * **Return root = new TreeNode(nums\[mid]);**
    * **Root.left = helper(nums, left, mid - 1);**
    * **Root.right = helper(nums, mid + 1, right);**
  * **pre-order → build tree**
  * **post-order array → build tree**

[**109. Convert Sorted List to Binary Search Tree**](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)

* **Get size of the sorted list**
* **In recursive function:**
  * **TreeNode left = helper(0 to mid - 1)**
  * **find mid, construct the node by using mid**
  * **Node.left = left;**
  * **Node right = helper(mid + 1, end);**

[**297.Serialize and Deserialize Binary Tree**](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)

* **Construct a tree by using Root, left, right**
* **If (root == null) return “null” + “,”**
* **Str += String.valueOf(root.val) + “,”;    Str = helper(root.left, str); str = helper(root.right, str);**
* **When de-serialization, split str by “,” and convert to LinkedList;**
* **Construct root from the first value, remove first value from List**
* **Go left and right**

[**173. Binary Search Tree Iterator**](https://leetcode.com/problems/binary-search-tree-iterator/)

* BST to Linkedlist by using Inorder traversal, create an iterator from the linkedlist
* Stack
* Morris traversal. [Solution](https://leetcode.com/submissions/detail/227173829/), [Explanation](http://www.learn4master.com/algorithms/morris-traversal-inorder-tree-traversal-without-recursion-and-without-stack)

[**230. Kth Smallest Element in a BST**](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)

* **Stack**
* **Morris**
* [**Divide and conquer**](https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/63743/Java-divide-and-conquer-solution-considering-augmenting-tree-structure-for-the-follow-up)

[**285. Inorder Successor in BST**](https://leetcode.com/problems/inorder-successor-in-bst/)

* [**Recursive to get inorder Successor & predecessor**](https://leetcode.com/problems/inorder-successor-in-bst/discuss/72653/Share-my-Java-recursive-solution)
* **Iterative**

[**270. Closest Binary Search Tree Value**](https://leetcode.com/problems/closest-binary-search-tree-value/)

[**272. Closest Binary Search Tree Value II**](https://leetcode.com/problems/closest-binary-search-tree-value-ii/)

[**99. Recover Binary Search Tree**](https://leetcode.com/problems/recover-binary-search-tree/)

* [**In-order traversal**](https://leetcode.com/problems/recover-binary-search-tree/discuss/32535/No-Fancy-Algorithm-just-Simple-and-Powerful-In-Order-Traversal)
* **Morris Traversal**

[**156. Binary Tree Upside Down**](https://leetcode.com/problems/binary-tree-upside-down/)

Traverse to left and your returned non-null node is your new root. Connect the right of the current node to the left of the left node, connect current to the right of the left node. Erase root's left and right to null. Return new root.

```java
public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null) return null;
    if (root.left == null && root.right == null) {
        return root;
    }
    TreeNode newRoot = upsideDownBinaryTree(root.left);
    root.left.left = root.right;
    root.left.right = root;
    root.left = null;
    root.right = null;
    return newRoot;
}
```

**114. Flatten Binary Tree to Linked List**

**255. Verify Preorder Sequence in Binary Search Tree**

#### [**333. Largest BST Subtree**](https://leetcode.com/problems/largest-bst-subtree/)

Top-down method may take more than O(n) time. Use Bottom-up, and store if the branch is a BST, size of the BST, the min and max node. Return to the previous level. At each node:

* check if the left result and right result is a BST, if one of them is not, return the best count of left and right
* check if the curt.val exceed the range of left and right, if yes, return the best count of left and right
* return the result if current node is a root of a BST.

```java
    public int largestBSTSubtree(TreeNode root) {
        return helper(root).count;
    }
    
    private Result helper(TreeNode curt) {
        if (curt == null) return new Result(true, 0);
        Result L = helper(curt.left);
        Result R = helper(curt.right);
        Result res = new Result(false, Math.max(L.count, R.count));
        if (!L.isBST || !R.isBST) {
            return res;
        } 
        if ((L.max != null && L.max.val >= curt.val) 
            || (R.min != null && R.min.val <= curt.val)) {
            return res;
        }
        res.isBST = true;
        res.count = L.count + R.count + 1;
        res.max = R.max != null ? R.max : curt;
        res.min = L.min != null ? L.min : curt;
        return res;
    }
    
    
    class Result {
        int count;
        boolean isBST;
        TreeNode max;
        TreeNode min;
        public Result(boolean isBST, int count) {
            this.isBST = isBST;
            this.count = count;
            this.max = null;
            this.min = null;
        }
    }
```

**222. Count Complete Tree Nodes**

**105. Construct Binary Tree from Preorder and Inorder Traversal**

**106. Construct Binary Tree from Inorder and Postorder Traversal**

[**116 .Populating Next Right Pointers in Each Node**](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)

**Level order traversal, use a Prev == null before each level, if (prev != null) prev.next = curt, then curt = prev;**<br>

[**314. Binary Tree Vertical Order Traversal**](https://leetcode.com/problems/binary-tree-vertical-order-traversal/)

* **Use Map\<Integer, List\<Integer>> to store col and related nodes;**
  * **Add two queues, one to store nodes, the other one to store col, poll from two nodes at the same time. Default col with 0;**
  * **Keep a min and max to store the min and max col number**
  * **Convert the map to List\<List\<Integer>>**

[**95. Unique Binary Search Trees II**](https://leetcode.com/problems/unique-binary-search-trees-ii/)

**用从1到N的数Construct所有Unique的BST**

* **If n == 0 return empty result**
* **Use helper function to iterate i through from 1 to n. Use another two iterations from 1 to i - 1 to create lefts and and i + 1 to n to create rights. Create node by using i, then attach root.left as left, root.right as right.**

[**331. Verify Preorder Serialization of a Binary Tree**](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/)

* [**Count indegree & outdegree**](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78552/JAVA-Counting-Indegree-and-Outdegree-SIMPLE-and-CLEAR!)
* **Using stack**

#### [1110. Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest/)

Bottom-up approach. If curt need to be deleted, add left and right to the list.

{% tabs %}
{% tab title="Java" %}

```java
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> set = new HashSet<>();
        for (int node : to_delete) {
            set.add(node);
        }
        List<TreeNode> res = new ArrayList<>();
        root = helper(root, set, res);
        if (root != null) res.add(root);
        return res;
    }
     
    private TreeNode helper(TreeNode curt,
                        Set<Integer> toDelete, 
                        List<TreeNode> list) {
        if (curt == null) return null;
        TreeNode L = helper(curt.left, toDelete, list);
        TreeNode R = helper(curt.right, toDelete, list);
        if (toDelete.contains(curt.val)) {
            if (L != null) list.add(L);
            if (R != null) list.add(R);
            return null;
        } 
        curt.left = L;
        curt.right = R;
        return curt;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        res = []
        self.helper(root, to_delete, res)
        if root.val not in to_delete:
            res.append(root)
        return res
    
    def helper(self, root, to_delete, res):
        if not root:
            return None;
        root.left = self.helper(root.left, to_delete, res)
        root.right = self.helper(root.right, to_delete, res)
        if root.val in to_delete:
            if root.left:
                res.append(root.left)
            if root.right:
                res.append(root.right)
            return None
        else:
            return root
```

{% endtab %}
{% endtabs %}

#### [979. Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/)

```java
    int total = 0;
    public int distributeCoins(TreeNode root) {
        helper(root);
        return total;
    }
    
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int L = helper(root.left);
        int R = helper(root.right);
        int res = L + R + root.val;
        if (res == 1) {
            return 0;
        } 
        total += Math.abs(res - 1);
        return res - 1;
    }
```

#### [863. All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/)

Convert tree to graph and BFS level order traversal.

```java
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, Set<TreeNode>> map = new HashMap<>();
        traverse(root, null, map);
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        q.offer(target);
        visited.add(target.val);
        while (!q.isEmpty() && K >= 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curt = q.poll();
                if (K == 0) res.add(curt.val);
                if (map.get(curt) != null) {
                    for (TreeNode next : map.get(curt)) {
                        if (visited.contains(next.val)) continue;
                        visited.add(next.val);
                        q.offer(next);
                    }
                }
            }
            K--;
        }
        return res;
    }
    
    private void traverse(TreeNode curt, TreeNode parent, Map<TreeNode, Set<TreeNode>> map) {
        if (curt == null) return;
        map.putIfAbsent(curt, new HashSet<>());
        map.putIfAbsent(parent, new HashSet<>());
        if (parent != null) {
            map.get(curt).add(parent);
            map.get(parent).add(curt);
        }
        traverse(curt.left, curt, map);
        traverse(curt.right, curt, map);
    }
```

#### [1145. Binary Tree Coloring Game](https://leetcode.com/problems/binary-tree-coloring-game/)

Count left and right children's nodes of the player 1's initial node with value `x`. Lets call `countLeft` and `countRight`.

`count` will recursively count the number of nodes,\
in the left and in the right.\
`n - countLeft - countRight` will be the number of nodes in the "subtree" of parent.\
Now we just need to compare `max(left, right, parent)` and `n / 2`

```java
int countLeft = 0, countRight = 0;
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
    int count = count(root, x);
    return Math.max(Math.max(countLeft, countRight), 
                    n - countLeft - countRight - 1) > n / 2;
}

private int count(TreeNode root, int x) {
    if (root == null) {
        return 0;
    }
    int L = count(root.left, x);
    int R = count(root.right, x);
    if (root.val == x) {
        countLeft = L;
        countRight = R;
    }
    return L + R + 1;
} 
```

#### [671. Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/)

```java
long res = Long.MAX_VALUE;
int min;
public int findSecondMinimumValue(TreeNode root) {
    min = root.val;
    dfs(root);
    return res == Long.MAX_VALUE ? -1 : (int)res;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    if (root.val < res && root.val > min) {
        res = root.val;
    }
    dfs(root.left);
    dfs(root.right);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.