# Tree Structure

## 101. Symmetric Tree [x]

https://leetcode.com/problems/symmetric-tree/description/

## 100. Same Tree [x]

https://leetcode.com/problems/same-tree/description/

## 98. Validate Binary Search Tree

• BST 条件
1. left < root < right
1. left and right subtree has to be valid BST

# Lowest Common Ancestor

## 235. Lowest Common Ancestor of a Binary Search Tree

• proning is possible via BST property

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

## 236. Lowest Common Ancestor of a Binary Tree

• root is LCA when left and right is not null
• pass LCA up to the real root as the return value

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

• 如果输入的node不在树里面怎么办
• 如果两个node是相同的怎么办

# Depth/Height/Path

## 104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

### iterative

Iterative approach has DFS and BFS.
DFS go through each of the leave node and update a global max along the way.
BFS maintains a count to record the max level when doing level order traversal, which the count is the max depth.

## 111. Minimum Depth of Binary Tree

• careful to the difference from max depth above
• BFS might works better than DFS since it is looking for the first leave node

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

### BFS iterative (preferred)

• first leave node with both left == null and right == null

## 110. Balanced Binary Tree [x]

https://leetcode.com/problems/balanced-binary-tree/description/

## 112. Path Sum

https://leetcode.com/problems/path-sum/description/

• path sum requires to check if current root is a leaf node (import)

### iterative: preorder traversal [x]

Similar solution as yours. Your solution has changed the internal tree node value, and in production code, this may be not permitted. Followed is my solution:

## 543. Diameter of Binary Tree

• diameter is number of edges between two nodes
• passing root is NOT required

https://leetcode.com/problems/diameter-of-binary-tree/description/

## 124. Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

• definition of path is same as lc543 Diameter of Binary Tree
• path sum return node value, hence, need to consider negative node value

Note: Iterative approach is also possible with post-order traversal but less straight forward in code aspect

# Binary Search Tree (BST)

## 230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

• method1: inorder traversal of BST returns the k-th smallest with list.get(k-1)
• method2: count total of node and use binary search to locate kth element

## 173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/description/

• inorder traversal for BST returns a sorted list

# Tree Traversal

## Preorder

https://leetcode.com/problems/binary-tree-preorder-traversal/description/

### Iterative w/ Guide Class

• use Guide class helps to improve code reusabliity and flexibility
• ops should be reversely pushed into stack

## Inorder

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

### Iterative w/ Guide Class

• use Guide class helps to improve code reusabliity and flexibility
• ops should be reversely pushed into stack

## Postorder

https://leetcode.com/problems/binary-tree-postorder-traversal/description/

### Iterative v1

• indeed the reverse order of level-order traversal
• since does NOT required output to be level ordred (just single list), use stack instead

### Iterative w/ Guide Class

• use Guide class helps to improve code reusabliity and flexibility
• ops should be reversely pushed into stack

## Levelorder

### 102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

### 103. Binary Tree Zigzag Level Order Traversal

• same to level order, reverse list order on ODD level

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

# Tree Reconstruction

## 297. Serialize and Deserialize Binary Tree

### DFS prefered (preorder traversal)

• preferred cuz less code complexity
• any one kind of traversal should work
• buildString() buildTree() method
• buildString with pre-order traversal
• using StringBuilder for buildString()
• using Queue for buildTree()
• why this work? since both buildString() & buildTree() uses the same pre-order traversal, which garntee the results are the same

## 449. Serialize and Deserialize BST

• as compact as possible (wo/ X or #)
• using two traverals (eg. preorder + inorder) to reconstruct
• solution 297 should also work for this porblem but less effiicent in space

### One traversal (preorder + BST property)

Since it is a BST, first value larger than root belongs to right subtree. we can use this property to reconstruct BST with just single traversal

Important takehome:

• BST can be reconstructed with ONE preorder traversal + BST property
• Binary Tree required at least TWO traversals we cannot take advantage of BST property

## 105. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

Observations:

1. preorder: first element of preorder is always the root of current subtree
1. inorder: once root found, in inorder array, left of root is left subtree, and right of root is right subtree.
1. preorder: Once we know the number of elements in left subtree and right subtree, we could find the corresponding roots for left subtree and right subtree from preorder array.
1. recursively repeat step 1-3.

Implementations:

• the hardest part of this question is to determine what indices are needed for the helper function
• inStart and inEnd indicates the range of current subtree in inorder array
• pStart tells the location of the root for current subtree (preorder[pStart])

## 106. Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

• note: postStart here is acutally the last element in ordering of the subtree

## Logs

• 06/02/2018: first draft finished
• 07/11/2018: revisited all questions & checked LC discussion
• 11/08/2018: add DFS approach for serialize & deserialize BST
• 05/11/2019: add Difference between #297 and #449 (serialize and deserialize BST & BT)
• 09/08/2019: updated binary tree & BST reconstruction