Many binary tree problems are about how to traversal it. In both recursive or non-recursive ways.

Binary Tree Traversal: Preorder, Inorder, Postorder, Level Order, Vertical Order, Right-Middle-Left, etc.

Only get the rightmost node at each level. Only get the leftmost node at each level, etc.

We might also see interesting requirements about updating binarytree. e,g, add a pointer to next, correct two nodes, delete a node, etc.

**Basic Abstractions**

Name | Summary |

**Scenarios**

**Code Skeleton**

**Questions**

Name | Example |
---|---|

Whether or not checking node is null |

// In-order traversal // terminate when node is null // function calls against both non-null pointers and null pointers void inorder(node *r) { if (r == NULL) return; inorder(r->left); printf("%d", r->data); inorder(r->right); }

// In-order traversal // terminate when node is null or a leaf // function calls against non-null pointers only void inorder(node *r) { if (r == NULL) return; if (r->left != NULL) { inorder(r->left); } printf("%d", r->data); if (r->right != NULL) { inorder(r->right); } }

Personally I like level-order (or BFS) very much.

(See all bfs problems: #bfs)

Q: How to time complexity for tree problems?

Q: Do you know the difference between level-order vs BFS(Breadth-first search)?

level-order traversal is the same as breadth-first traversal. There are many reasons to traverse something, it doesn't just have to be to search, as breadth-first search seems to imply, although many (or most) don't make that distinction and use the terms interchangeably. From link: https://stackoverflow.com/questions/23576746/what-is-the-difference-between-breadth-first-searching-and-level-order-traversal

Examine previous/next node for in-order traversal. Closest Binary Search Tree Value.

The most impressive problems to me:

See all binarytree problems: #binarytree.

- Review: Binary Tree Problems
- LintCode: The Biggest Score On The Tree
- LintCode: Binary Tree Maximum Node
- Leetcode: Validate Binary Search Tree
- Leetcode: Unique Binary Search Trees
- Leetcode: Trim a Binary Search Tree
- Leetcode: Sum Root to Leaf Numbers
- Leetcode: Sum of Left Leaves
- Leetcode: Subtree of Another Tree
- Leetcode: Smallest Subtree with all the Deepest Nodes
- Leetcode: Serialize and Deserialize BST
- Leetcode: Serialize and Deserialize Binary Tree
- Leetcode: Second Minimum Node In a Binary Tree
- Leetcode: Search in a Binary Search Tree
- Leetcode: Same Tree
- Leetcode: Recover Binary Search Tree
- Leetcode: Range Sum of BST
- Leetcode: Quad Tree Intersection
- Leetcode: Populating Next Right Pointers in Each Node II
- Leetcode: Populating Next Right Pointers in Each Node
- Leetcode: Path Sum IV
- Leetcode: Path Sum III
- Leetcode: Path Sum II
- Leetcode: Path Sum
- Leetcode: Path In Zigzag Labelled Binary Tree
- Leetcode: Most Frequent Subtree Sum
- Leetcode: Minimum Depth of Binary Tree
- Leetcode: Minimum Cost Tree From Leaf Values
- Leetcode: Minimum Absolute Difference in BST
- Leetcode: Merge Two Binary Trees
- Leetcode: Maximum Width of Binary Tree
- Leetcode: Maximum Depth of Binary Tree
- Leetcode: Maximum Binary Tree
- Leetcode: Lowest Common Ancestor of Deepest Leaves
- Leetcode: Lowest Common Ancestor of a Binary Search Tree
- Leetcode: Longest Univalue Path
- Leetcode: Largest BST Subtree
- Leetcode: Invert Binary Tree
- Leetcode: Insufficient Nodes in Root to Leaf Paths
- Leetcode: Insert into a Binary Search Tree
- Leetcode: Flatten Binary Tree to Linked List
- Leetcode: Find Mode in Binary Search Tree
- Leetcode: Find Leaves of Binary Tree
- Leetcode: Find Duplicate Subtrees
- Leetcode: Equal Tree Partition
- Leetcode: Diameter of Binary Tree
- Leetcode: Delete Node in a BST
- Leetcode: Cousins in Binary Tree
- Leetcode: Count Complete Tree Nodes
- Leetcode: Convert Sorted List to Binary Search Tree
- Leetcode: Convert Sorted Array to Binary Search Tree
- Leetcode: Convert BST to Greater Tree
- Leetcode: Construct String from Binary Tree
- Leetcode: Construct Quad Tree
- Leetcode: Construct Binary Tree from Preorder and Postorder Traversal
- Leetcode: Complete Binary Tree Inserter
- Leetcode: Closest Binary Search Tree Value II
- Leetcode: Closest Binary Search Tree Value
- Leetcode: Boundary of Binary Tree
- Leetcode: Binary Trees With Factors
- Leetcode: Binary Tree Vertical Order Traversal
- Leetcode: Binary Tree Upside Down
- Leetcode: Binary Tree Tilt
- Leetcode: Binary Tree Right Side View
- Leetcode: Binary Tree Pruning
- Leetcode: Binary Tree Preorder Traversal
- Leetcode: Binary Tree Postorder Traversal
- Leetcode: Binary Tree Paths
- Leetcode: Binary Tree Maximum Path Sum
- Leetcode: Binary Tree Longest Consecutive Sequence II
- Leetcode: Binary Tree Longest Consecutive Sequence
- Leetcode: Balanced Binary Tree
- Leetcode: Average of Levels in Binary Tree
- Leetcode: All Possible Full Binary Trees
- Leetcode: Add One Row to Tree
- Find Largest Value in Each Tree Row

See more blog_posts.