# Tree

## Tree

## 1. Traversal

### (1) Preorder Traversal

```java
    // Iterative version
    public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();

       if (root == null) {
           return res;
       }

       Stack<TreeNode> stack = new Stack<>();
       stack.push(root);

       while (!stack.isEmpty()) {
           TreeNode curNode = stack.pop();
           res.add(curNode.val);

           if (curNode.right != null) {
               stack.push(curNode.right);
           }

           if (curNode.left != null) {
               stack.push(curNode.left);
           } 
       }
       return res;
    }
```

### (2) Inorder Traversal

```java
    // Iterative version
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curNode = root;

        Stack<TreeNode> stack = new Stack<>();
        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            else {
                curNode = stack.pop();
                res.add(curNode.val);
                curNode = curNode.right;
            }
        }
        return res;
    }
```

### (3) Postorder Traversal

```java
    // Iterative version
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode curNode = null, preNode = null;

        while (!stack.isEmpty()) {
            curNode = stack.peek();
            // Case 1: Traverse down the tree, put left child into stack if it exists, otherwise put right child
            if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
                if (curNode.left != null) {
                    stack.push(curNode.left);
                }
                else if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 2: Travese up from left child
            else if (curNode.left == preNode) {
                if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 3: Traverse up from right child
            else {
                res.add(curNode.val);
                stack.pop();
            }
            preNode = curNode;
        }
        return res;
    }
```

## 2. DFS and BFS in Tree

### (1) BFS

This is essentially [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/?tab=Description)

```java
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> level = null;

        while (!queue.isEmpty()) {
            int size = queue.size();
            level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();

                level.add(curNode.val);

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            res.add(level);
        }
        return res;
    }
```

### **(2) DFS**

* DFS is helpful to get the size of subtree: [Largest BST Subtree](https://leetcode.com/problems/largest-bst-subtree/?tab=Description)

```java
    public int getTreeSize(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSize = getTreeSize(node.left);
        int rightSize = getTreeSize(node.right);

        return 1 + leftSize + rightSize;
    }
```

* DFS is helpful to get the height of subtree: [Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/?tab=Description)

```java
    public int getTreeHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = getTreeHeight(node.left);
        int rightHeight = getTreeHeight(node.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }
```

## 3. Binary Search Tree

1. Check if a tree is binary search tree: [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/?tab=Description)
2. Based on the property of Binary Search Tree, we can implement **Binary Search** to retrieve a value: [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/?tab=Description%29,%20\[Closest%20Binary%20Search%20Tree%20Value]%28https://leetcode.com/problems/closest-binary-search-tree-value/?tab=Description)

## 4.Threaded Tree (Morris Tree)

Threaded Tree can guarantee **O(n) time** in traversal and **O(1) space**

### (1) Preorder Traversal

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

       TreeNode curNode = root;
       TreeNode preNode = null;

       while (curNode != null) {
           if (curNode.left == null) {
               res.add(curNode.val);
               curNode = curNode.right;
           }
           else {
               preNode = curNode.left;
               // Get the predecessor of curNode
               while (preNode.right != null && preNode.right != curNode) {
                   preNode = preNode.right;
               }

               // Case 1: Find the predecessor of curNode, traversing down
               if (preNode.right == null) {
                   res.add(curNode.val);
                   preNode.right = curNode;
                   curNode = curNode.left;
               }
               // Case 2: Disconnect with predecessor, traversing up
               else {
                   preNode.right = null;
                   curNode = curNode.right;
               }
           }
       }
       return res;
    }
```

### (2) Inorder Traversal

```java
TreeNode preNode = null;
        TreeNode curNode = root;

        while (curNode != null) {
            if (curNode.left == null) {
                res.add(curNode.val);
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null && preNode.right != curNode) {
                    preNode = preNode.right;
                }

                if (preNode.right == null) {
                    preNode.right = curNode;
                    curNode = curNode.left;
                }
                else {
                    preNode.right = null;
                    res.add(curNode.val);
                    curNode = curNode.right;
                }
            }
        }
        return res;
```

### (3) Postorder Traversal

```java
List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        TreeNode dummy = new TreeNode(0);
        TreeNode preNode = null, curNode = dummy;
        dummy.left = root;

        while (curNode != null) {
            if (curNode.left == null) {
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null && preNode.right != curNode) {
                    preNode = preNode.right;
                }

                // Traversing down
                if (preNode.right == null) {
                    preNode.right = curNode;
                    curNode = curNode.left;
                }
                // Traversing up, reverse the path
                else {
                    TreeNode node = preNode;
                    reverse(curNode.left, preNode);
                    while (node != curNode.left) {
                        res.add(node.val);
                        node = node.right;
                    }
                    res.add(node.val); // node is now equal to curNode.left
                    reverse(preNode, curNode.left);
                    preNode.right = null;
                    curNode = curNode.right;
                }
            }
        }
        return res;
    }

    public void reverse(TreeNode from, TreeNode to) {
        if (from == to) {
            return;
        }

        TreeNode preNode = from, curNode = from.right, nextNode = null;

        while (preNode != to) {
            nextNode = curNode.right;
            curNode.right = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
    }
```

## 5. Question Category

1. Preorder Traversal: [Serialize and Deserialize Binary Tree, ](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/?tab=Description%29%20\[Serialize%20and%20Deserialize%20BST]%28https://leetcode.com/problems/serialize-and-deserialize-bst/?tab=Description)
2. Inorder Traversal: [Recover Binary Search Tree, ](https://leetcode.com/problems/recover-binary-search-tree/?tab=Description%29\[Binary%20Search%20Tree%20Iterator]%28https://leetcode.com/problems/binary-search-tree-iterator/?tab=Description%29,%20\[Closest%20Binary%20Search%20Tree%20Value%20II]%28https://leetcode.com/problems/closest-binary-search-tree-value-ii/?tab=Description)
3. Postorder Traversal: [Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/?tab=Description%29,%20\[Most%20Frequent%20Subtree%20Sum,%20]%28https://leetcode.com/problems/most-frequent-subtree-sum/?tab=Description%29\[Count%20Univalue%20Subtrees]%28https://leetcode.com/problems/count-univalue-subtrees/?tab=Description)