# 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

![](/files/-MjWcLjC8YC2hJYaunua)

### Pre-order

<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/>

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/>

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>

## Serialization and deserialization

<https://leetcode.com/problems/find-duplicate-subtrees> <https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/>\
<https://leetcode.com/problems/serialize-and-deserialize-bst>\
<https://leetcode.com/problems/construct-string-from-binary-tree>\
<https://leetcode.com/problems/construct-binary-tree-from-string>

## DFS or BFS?

### BFS: level

* [662-Maximum Width of Binary Tree](/leetcode/topics/tree.md)

### DFS: go through a path

* [437-Path Sum III](/leetcode/topics/tree.md)
* [687-Longest Univalue Path](/leetcode/topics/tree.md)

## 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>. `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://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/>

### 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

![](/files/-M9t-7eShFaHR_Ek_lqG) ![](/files/-M9t-7eTjYf_Ba_vCifd) ![](/files/-M9t-7eUaDANprNb5Z_v) ![](/files/-M9t-7eV_yJDdR7e1Fik)

<https://leetcode.com/problems/range-sum-query-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/count-of-smaller-numbers-after-self> <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/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/count-univalue-subtrees/description/> <https://leetcode.com/problems/subtree-of-another-tree/description/>


---

# 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://jaywin.gitbook.io/leetcode/topics/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.