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.

Num | Problem | Summary |
---|---|---|

1 | Binary Tree Level Order Traversal | LeetCode: Binary Tree Right Side View |

2 | Tree Traversal: Binary Tree Vertical Order Traversal | LeetCode: Binary Tree Vertical Order Traversal |

3 | Tree Traversal: Find Leaves of Binary Tree | Leetcode: Find Leaves of Binary Tree |

4 | Get binary tree height, width | LeetCode: Balanced Binary Tree |

5 | LCA – Lowest Common Ancestor of a binary Tree | LeetCode: Lowest Common Ancestor of a Binary Tree |

6 | Validate Binary Search Tree | LeetCode: Validate Binary Search Tree |

7 | Construct binary tree | LeetCode: Construct Binary Tree from Preorder and Postorder Traversal |

8 | Distribute Coins in Binary Tree | LeetCode: Distribute Coins in Binary Tree |

9 | Binary Tree Vertical Order Traversal | LeetCode: Binary Tree Vertical Order Traversal |

10 | Verify Preorder Sequence in Binary Search Tree | LeetCode: Verify Preorder Sequence in Binary Search Tree |

11 | Recursive + Greedy | LeetCode: Binary Tree Coloring Game |

12 | Binary tree + greedy | LeetCode: Binary Tree Cameras |

13 | Revert binary tree between left and right | |

14 | binary tree serialization and deserialization | |

15 | Morris tree trasversal | |

16 | Find the next node of binary search tree | |

17 | Count Complete Tree Nodes | LeetCode: Count Complete Tree Nodes |

18 | Binary Tree Upside Down | Leetcode: Binary Tree Upside Down |

19 | Closest Binary Search Tree Value II | Leetcode: Closest Binary Search Tree Value II |

// 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.

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: Verify Preorder Sequence in Binary Search Tree
- LeetCode: Validate Binary Tree Nodes
- 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: Pseudo-Palindromic Paths in a Binary Tree
- 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 Product of Splitted 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: Kth Ancestor of a Tree Node
- 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: Find a Corresponding Node of a Binary Tree in a Clone of That Tree
- LeetCode: Equal Tree Partition
- LeetCode: Diameter of Binary Tree
- LeetCode: Delete Node in a BST
- LeetCode: Cousins in Binary Tree
- LeetCode: Count Good Nodes 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: Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
- 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: Binary Tree Coloring Game
- LeetCode: Binary Tree Cameras
- 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.