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


---

# 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://protegejj.gitbook.io/my-algorithm-summary/data-structure/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.