# Tree

## Key points

* Traversal:
  * pre-order, in-order, post-order
  * Two approaches: 1) DFS, 2) Iteration
* Divide & Conquer VS Traversal:
  * DC: one send left & right two people to get the result, and then do sth.
  * T: one with a notebook walk through the tree
* BST, Binary Search Tree:
  * in-order is a sorted list, important !
  * left < root < right, not duplicate
  * use `TreeSet` or `TreeMap`
* Tricks:
  * isLeaf(): root.left == null && root.right == null
  * every node: 1)root == null 2) root.left == null 3)root.right == null
* Binary Indexed Tree:
  * the sum of (0, i), in O(logn) time.
* Segment Tree:
  * sum/minimum in a range

## Traverse

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-45d7e9353fa669bf38897b8bec59b0e5465b5858%2Fimage.png?alt=media)

### Pre-order

[https://leetcode.com/problems/binary-tree-preorder-traversal/](https://leetcode.com/problems/binary-tree-preorder-traversal/)

Iterative

```java
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> res = new LinkedList<Integer>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                res.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode head = stack.pop();
            curr = head.right;
        }

        return res; 
    }
}
```

Recursive

```java
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<Integer>();

        traverse(root, res);

        return res; 
    }

    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;

        res.add(root.val);
        traverse(root.left, res);
        traverse(root.right, res);
    }
}
```

### In-order

[https://leetcode.com/problems/binary-tree-inorder-traversal/](https://leetcode.com/problems/binary-tree-inorder-traversal/)

Iterative

```java
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> res = new LinkedList<Integer>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode head = stack.pop();
            res.add(head.val);
            curr = head.right;
        }

        return res; 
    }
}
```

Recursive

```java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<Integer>();

        traverse(root, res);

        return res; 
    }

    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;

        traverse(root.left, res);
        res.add(root.val);
        traverse(root.right, res);
    }
}
```

### Post-order

[https://leetcode.com/problems/binary-tree-postorder-traversal/](https://leetcode.com/problems/binary-tree-postorder-traversal/)

Iterative

```java
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        LinkedList<Integer> res = new LinkedList<Integer>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                res.addFirst(curr.val); // Revered of pre-order
                stack.push(curr);
                curr = curr.right; // Revered of pre-order
            }
            TreeNode head = stack.pop();
            curr = head.left; // Revered of pre-order
        }

        return res; 
    }
}
```

Recursive

```java
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<Integer>();

        traverse(root, res);

        return res; 
    }

    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;

        traverse(root.left, res);        
        traverse(root.right, res);
        res.add(root.val);
    }
}
```

Reference: [https://discuss.leetcode.com/topic/30632/preorder-inorder-and-postorder-iteratively-summarization](https://discuss.leetcode.com/topic/30632/preorder-inorder-and-postorder-iteratively-summarization)

## Serialization and deserialization

[https://leetcode.com/problems/find-duplicate-subtrees](https://leetcode.com/problems/find-duplicate-subtrees) [https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/)\
[https://leetcode.com/problems/serialize-and-deserialize-bst](https://leetcode.com/problems/serialize-and-deserialize-bst)\
[https://leetcode.com/problems/construct-string-from-binary-tree](https://leetcode.com/problems/construct-string-from-binary-tree)\
[https://leetcode.com/problems/construct-binary-tree-from-string](https://leetcode.com/problems/construct-binary-tree-from-string)

## DFS or BFS?

### BFS: level

* [662-Maximum Width of Binary Tree](tree)

### DFS: go through a path

* [437-Path Sum III](tree)
* [687-Longest Univalue Path](tree)

## Common law

```
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
```

Array -> Complete Binary Tree: parent i, left 2i+1, right 2i+2

### Types of Binary Tree

* Full Binary Tree
* Complete Binary Tree

![](http://www.csie.ntnu.edu.tw/~u91029/BinaryTree2.png)

*   Binary Search Tree: `left < root < right`

    use `TreeSet` to implement BST: [https://leetcode.com/problems/contains-duplicate-iii](https://leetcode.com/problems/contains-duplicate-iii). `TreeSet` is implemented by Black-Red Tree, self balanced. `insert`,`delete`, `search` in `O(logN)` complexity.

![](https://i.stack.imgur.com/36FkR.png)

* AVL Tree: `|left height - right height| <= 1`

![](https://i.stack.imgur.com/0kXfL.png)

* Heap: Max Heap, Min Heap. Heap is complete binary tree.

Priority Queue is a Heap, implemented using an Array `object[]`. More details about `heapify`: [https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/023-merge-k-sorted-lists.html](https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/023-merge-k-sorted-lists.html) ![](https://algs4.cs.princeton.edu/24pq/images/heap-ops.png)

## Segment Tree

* the leaves are values of nums

![](https://www.geeksforgeeks.org/wp-content/uploads/segment-tree1.png)

[https://leetcode.com/problems/range-sum-query-mutable/description/](https://leetcode.com/problems/range-sum-query-mutable/description/)

### ac2: Segment Tree

more intuitive, yet more code. Notice: use divide and conquer, no need to care about the mid point unless building the tree.

```java
class NumArray {

    class SegTreeNode{
        int start, end, sum;
        SegTreeNode left, right;
        public SegTreeNode(int start, int end){
            this.start = start;
            this.end = end;
            sum = 0;
        }
    }

    SegTreeNode root;

    public NumArray(int[] nums) {
        root = build(nums, 0, nums.length-1);
    }
    private SegTreeNode build(int[] nums, int start, int end) {
        if (start < 0 || end >= nums.length || start > end) return null;

        int mid = start + (end - start) / 2;
        SegTreeNode node = new SegTreeNode(start, end);
        if (start == end) {
            node.sum = nums[start];
        } else {
            node.left = build(nums, start, mid);
            node.right = build(nums, mid+1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

    public void update(int i, int val) {
        update(root, i, val);
    }
    private void update(SegTreeNode root, int i, int val) {
        if (i < root.start || i > root.end) return; // out of range
        if (root.start == root.end) {
            root.sum = val; // leaf, sum = nums[i]
            return;
        }

        // divide and conquer
        update(root.left, i, val);
        update(root.right, i, val);
        root.sum = root.left.sum + root.right.sum;  
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }
    private int sumRange(SegTreeNode root, int i, int j) {
        if (i > root.end || j < root.start) return 0; // out of range
        if (i <= root.start && root.end <= j) return root.sum;  // current node within range, return value

        // divide and conquer
        int res = 0;
        res += sumRange(root.left, i, j);
        res += sumRange(root.right, i, j);
        return res;
    }

}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
```

## Binary Indexed Tree

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-8bd5517a7c2b8cf838032d85e10a87676bbeb163%2FBIT1.png?alt=media) ![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-870f7b240d33f74aa8a78c7f82ce761962ac0d4d%2Fbit2.png?alt=media) ![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-10dd0eded3242f8a356082e3950eb90341061dd4%2Fbit3.png?alt=media) ![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-c504fa9e2e3e5597167489816247560185a73a95%2Fbit4.png?alt=media)

[https://leetcode.com/problems/range-sum-query-mutable/description/](https://leetcode.com/problems/range-sum-query-mutable/description/) [https://leetcode.com/problems/range-sum-query-2d-mutable/description/](https://leetcode.com/problems/range-sum-query-2d-mutable/description/)

### ac1: Binary Indexed Tree

careful: bit.length = nums.length + 1; so need to do `i++` in methods

```java
class NumArray {
    int[] bit;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            nums[i] = 0;
            update(i, val);
        }
    }

    public void update(int i, int val) {
        // index + last '1' bit 
        int diff = val - nums[i];
        nums[i] = val;

        i++;
        while (i < bit.length) {
            bit[i] += diff;
            i += i & (-i);
        }
    }

    private int getSum(int i) {
        // index - last '1' bit 
        i++;
        int res = 0;
        while (i > 0) {
            res += bit[i];
            i -= i & (-i);
        }
        return res;
    }

    public int sumRange(int i, int j) {
        return getSum(j) - getSum(i-1);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
```

[https://leetcode.com/problems/reverse-pairs/description/](https://leetcode.com/problems/reverse-pairs/description/) [https://leetcode.com/problems/count-of-smaller-numbers-after-self](https://leetcode.com/problems/count-of-smaller-numbers-after-self) [https://leetcode.com/problems/count-of-range-sum](https://leetcode.com/problems/count-of-range-sum)

## Binary Search Tree

in-order asecending [https://leetcode.com/problems/validate-binary-search-tree/description/](https://leetcode.com/problems/validate-binary-search-tree/description/) [https://leetcode.com/problems/kth-smallest-element-in-a-bst/](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)

## Divide & Conquer

get result from children, then do something

[https://leetcode.com/problems/longest-univalue-path/description/](https://leetcode.com/problems/longest-univalue-path/description/) [https://leetcode.com/problems/count-univalue-subtrees/description/](https://leetcode.com/problems/count-univalue-subtrees/description/) [https://leetcode.com/problems/subtree-of-another-tree/description/](https://leetcode.com/problems/subtree-of-another-tree/description/)
