# Trees

## Types of Binary Trees

<https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees>

A **full** binary tree is a tree in which every node has either 0 or 2 children.

In a **complete** binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

A **balanced** binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

A **perfect** binary tree is a tree with all leaves are at the same level, and every parent has two children.

## Binary Tree Node

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
```

## Binary Tree Traversal

### **Iterative, Non-recursive Implementation with Stack**

#### Pre-Order Traversal

```java
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;   
        }
    }
    return result;
}
```

\*Another Iterative Pre-Order Traversal

```java
public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ans;
    }
```

#### In-Order Traversal

```java
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;   
        }
    }
    return result;
}
```

\*Another Iterative In-Order Traversal

```java
public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            ans.add(p.val);
            p = p.right;
        }
        return ans;
    }
```

#### Post-Order Traversal

```java
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}
```

\*Another Iterative Post-Order Traversal

```java
public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.addFirst(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return output;
    }
```

### Recursive Implementation

#### Pre-Order Traversal

```java
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        recursivePreorderTraversal(root, result);
        return result;
    }
    void recursivePreorderTraversal(TreeNode root, List<Integer> result) {
        if (root != null) {
            result.add(root.val);
            recursivePreorderTraversal(root.left, result);
            recursivePreorderTraversal(root.right, result);
        }
    }
}
```

#### In-Order Traversal

```java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        recursiveInorderTravesal(root, result);
        return result;
    }
    void recursiveInorderTravesal(TreeNode root, List<Integer> result) {
        if (root != null) {
            if (root.left != null) {
                recursiveInorderTravesal(root.left, result);
            }
            result.add(root.val);
            if (root.right != null) {
                recursiveInorderTravesal(root.right, result);
            }
        }
    }
}
```

#### Post-Order Traversal

```java
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        recursivePreorderTraversal(root, result);
        return result;
    }
    void recursivePreorderTraversal(TreeNode root, List<Integer> result) {
        if (root != null) {
            recursivePreorderTraversal(root.left, result);
            recursivePreorderTraversal(root.right, result);
            result.add(root.val);
        }
    }
}
```

### Level Order Traversal

#### BFS

```java
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

        if(root == null) return wrapList;

        queue.offer(root);
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();
            for(int i=0; i<levelNum; i++) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(subList);
        }
        return wrapList;
    }
}
```

#### DFS

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        levelOrderHelper(root, 0, result);
        return result;
    }
    void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        if (depth == result.size()) {
            result.add(new ArrayList<Integer>());
        }
        result.get(depth).add(root.val);
        levelOrderHelper(root.left, depth + 1, result);
        levelOrderHelper(root.right, depth + 1, result);

    }
}
```

## Maximum Depth of Binary Tree

**Recursive**

```java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1 + Math.max(left, right);
    }
}
```

## **Symmetric Tree**

<https://leetcode.com/articles/symmetric-tree/>

**Recursive**

```java
public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}
boolean isMirror(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) return true;
    if (node1 == null || node2 == null) return false;
    if (node1.val != node2.val) return false;
    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
```

Iterative

```java
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Queue < TreeNode > q = new LinkedList < TreeNode > ();
    q.offer(root.left);
    q.offer(root.right);
    while (!q.isEmpty()) {
        TreeNode n1 = q.poll();
        TreeNode n2 = q.poll();
        if (n1 == null && n2 == null) continue;
        if (n1 == null && n2 != null) return false;
        if (n1 != null && n2 == null) return false;
        if (n1.val != n2.val) return false;
        q.offer(n1.left);
        q.offer(n2.right);
        q.offer(n1.right);
        q.offer(n2.left);
    }
    return true;
}
```

## Binary Search Tree (BST)

```java
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return isValidSubtree(root, null, null);
    }
    boolean isValidSubtree (TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if ((min != null && root.val <= min) ||  (max != null && root.val >= max)) return false;
        return isValidSubtree (root.left, min, root.val) && isValidSubtree(root.right, root.val, max);
    }
```


---

# 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://aaronice.gitbook.io/lintcode/trees.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.