Review: Binary Tree Problems Posted on January 22, 2018July 26, 2020 by braindenny 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. CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups (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: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups See all binarytree problems: #binarytree. Review: Binary Tree ProblemsLintCode: The Biggest Score On The TreeLintCode: Binary Tree Maximum NodeLeetCode: Verify Preorder Sequence in Binary Search TreeLeetCode: Validate Binary Tree NodesLeetCode: Validate Binary Search TreeLeetCode: Unique Binary Search TreesLeetCode: Trim a Binary Search TreeLeetCode: Sum Root to Leaf NumbersLeetCode: Sum of Left LeavesLeetCode: Subtree of Another TreeLeetCode: Smallest Subtree with all the Deepest NodesLeetCode: Serialize and Deserialize BSTLeetCode: Serialize and Deserialize Binary TreeLeetCode: Second Minimum Node In a Binary TreeLeetCode: Search in a Binary Search TreeLeetCode: Same TreeLeetCode: Recover Binary Search TreeLeetCode: Range Sum of BSTLeetCode: Quad Tree IntersectionLeetCode: Pseudo-Palindromic Paths in a Binary TreeLeetCode: Populating Next Right Pointers in Each Node IILeetCode: Populating Next Right Pointers in Each NodeLeetCode: Path Sum IVLeetCode: Path Sum IIILeetCode: Path Sum IILeetCode: Path SumLeetCode: Path In Zigzag Labelled Binary TreeLeetCode: Most Frequent Subtree SumLeetCode: Minimum Depth of Binary TreeLeetCode: Minimum Cost Tree From Leaf ValuesLeetCode: Minimum Absolute Difference in BSTLeetCode: Merge Two Binary TreesLeetCode: Maximum Width of Binary TreeLeetCode: Maximum Product of Splitted Binary TreeLeetCode: Maximum Depth of Binary TreeLeetCode: Maximum Binary TreeLeetCode: Lowest Common Ancestor of Deepest LeavesLeetCode: Lowest Common Ancestor of a Binary Search TreeLeetCode: Longest Univalue PathLeetCode: Largest BST SubtreeLeetCode: Kth Ancestor of a Tree NodeLeetCode: Invert Binary TreeLeetCode: Insufficient Nodes in Root to Leaf PathsLeetCode: Insert into a Binary Search TreeLeetCode: Flatten Binary Tree to Linked ListLeetCode: Find Mode in Binary Search TreeLeetCode: Find Leaves of Binary TreeLeetCode: Find Duplicate SubtreesLeetCode: Find a Corresponding Node of a Binary Tree in a Clone of That TreeLeetCode: Equal Tree PartitionLeetCode: Diameter of Binary TreeLeetCode: Delete Node in a BSTLeetCode: Cousins in Binary TreeLeetCode: Count Good Nodes in Binary TreeLeetCode: Count Complete Tree NodesLeetCode: Convert Sorted List to Binary Search TreeLeetCode: Convert Sorted Array to Binary Search TreeLeetCode: Convert BST to Greater TreeLeetCode: Construct String from Binary TreeLeetCode: Construct Quad TreeLeetCode: Construct Binary Tree from Preorder and Postorder TraversalLeetCode: Complete Binary Tree InserterLeetCode: Closest Binary Search Tree Value IILeetCode: Closest Binary Search Tree ValueLeetCode: Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreeLeetCode: Boundary of Binary TreeLeetCode: Binary Trees With FactorsLeetCode: Binary Tree Vertical Order TraversalLeetCode: Binary Tree Upside DownLeetCode: Binary Tree TiltLeetCode: Binary Tree Right Side ViewLeetCode: Binary Tree PruningLeetCode: Binary Tree Preorder TraversalLeetCode: Binary Tree Postorder TraversalLeetCode: Binary Tree PathsLeetCode: Binary Tree Maximum Path SumLeetCode: Binary Tree Longest Consecutive Sequence IILeetCode: Binary Tree Longest Consecutive SequenceLeetCode: Binary Tree Coloring GameLeetCode: Binary Tree CamerasLeetCode: Balanced Binary TreeLeetCode: Average of Levels in Binary TreeLeetCode: All Possible Full Binary TreesLeetCode: Add One Row to TreeFind Largest Value in Each Tree Row See more blog posts. Post Views: 3