Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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

linkedin
github
slack

Post Views: 3
Posted in ReviewTagged #binarytree, review

Post navigation

Review: Binary Search Problems
Review: Linked List Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.