Topic 08 of 15
Binary Trees
A family tree.
A binary tree is a family tree where every parent has at most two children. Almost every tree problem is the same move: ask the left child, ask the right child, and combine their answers. Reading it row by row uses a waiting line instead.
What you will be able to do
Preorder, inorder, postorderLevel order with a queueViews and boundariesHeights and diametersLowest common ancestor
0/35
Meet the binary tree
01 / 04
The root, 1, sits at the top. Its children are 2 and 3. Nodes with no children are leaves.
- looking now
- checking
- done
- answer
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Level order traversalRead a family tree one row at a time, from the grandparents down to the grandchildren, left to right.Breadth first search with a queue
- 02Reverse Level Order traversalRead a tree row by row starting from the bottom row, each row still from left to right, by stacking plates and taking them off the top.Breadth first search with a queue
- 03Height of a treeFind how many floors a family tree has by letting every person ask their two children how tall their part is.Depth first search
- 04Diameter of a treeFind the longest walk between any two nodes of a tree, by asking at every node how tall its two sides are.Depth first search
- 05Mirror of a treeTurn a tree into its reflection in a mirror by swapping the left and right child of every node.Depth first search
- 06Inorder Traversal of a tree both using recursion and IterationVisit every node of a tree as left side, then me, then right side, first with a helper that calls itself and then with your own pile of bookmarks.Iterative traversal with a stack
- 07Preorder Traversal of a tree both using recursion and IterationVisit every node of a tree as me first, then my left side, then my right side, with recursion and with your own pile of to-do cards.Iterative traversal with a stack
- 08Postorder Traversal of a tree both using recursion and IterationVisit every node of a tree as left side, then right side, then me last, with recursion and with one stack plus a note of who finished last.Iterative traversal with a stack
- 09Left View of a treeStand on the left side of a tree and write down the one person you can see on each floor.Depth first search
- 10Right View of TreeStand on the right side of a tree and write down the one person you can see on each floor.Depth first search
- 11Top View of a treeLook down at a tree from the sky, give every node a column number, and keep the highest node in each column.Breadth first search with a queue
- 12Bottom View of a treeLie under a tree and look up: in each column you only see the lowest node, so list those lowest nodes from left to right.Breadth first search with a queue
- 13Zig-Zag traversal of a binary treeRead a tree row by row like a snake: left to right on one row, right to left on the next, and keep switching.Two stacks
- 14Check if a tree is balanced or notCheck that at every node of a tree, the left side and the right side are about equally tall, never more than one step apart.Depth first search
- 15Diagonal Traversal of a Binary treeRead a tree in slanted lines: slide down to the right as far as you can, and save every left turn for the next slanted line.Breadth first search with a queue
- 16Boundary traversal of a Binary treeWalk around the outside of a tree like an ant on a fence: down the left edge, along every leaf at the bottom, then up the right edge.Depth first search
- 17Construct Binary Tree from String with Bracket RepresentationRead a string like 4(2(3)(1))(6(5)) and build the tree it describes, where each pair of brackets wraps one child.Recursive parsing
- 18Convert Binary tree into Doubly Linked ListTurn a tree into a two-way chain of the same nodes, in left to right order, by reusing the left and right arrows of each node as back and next.Inorder traversal with a prev pointer
- 19Convert Binary tree into Sum treeReplace every node with the total of all the old values below it, so leaves become 0 and parents hold the sums of their children.Depth first search
- 20Construct Binary tree from Inorder and preorder traversalRebuild a tree from two lists of its nodes: one that names each parent before its children, and one that reads the tree from left to right.Divide and conquer
- 21Find minimum swaps required to convert a Binary tree into BSTCount the fewest value swaps that turn a tree into a search tree, by reading it left to right and counting the loops of misplaced numbers.Cycle counting
- 22Check if Binary tree is Sum tree or notCheck that every parent in a tree holds exactly the total of everything below it, by adding up totals from the bottom.Depth first search
- 23Check if all leaf nodes are at same level or notCheck that every leaf of a tree sits on the same row, by remembering the row of the first leaf and comparing all the others to it.Depth first search
- 24Check if a Binary Tree contains duplicate subtrees of size 2 or moreFind out if a tree has two separate branches that look exactly the same and have at least two nodes each.Hash map of subtree shapesMust do
- 25Check if 2 trees are mirror or notCheck if one tree is the reflection of the other, by comparing each left side of one tree with the right side of the other.Depth first search
- 26Sum of Nodes on the Longest path from root to leaf nodeWalk every way from the top of a tree to the bottom, and report the total of the longest walk, using the bigger total when two walks are equally long.Depth first search
- 27Check if given graph is tree or notDecide if a bunch of dots joined by lines is a tree: everything connected, no loops, and exactly one line fewer than dots.Union findMust do
- 28Find Largest subtree sum in a treeFind the branch of a tree whose numbers add up to the most, by adding up every branch once from the bottom.Depth first search
- 29Maximum Sum of nodes in Binary tree such that no two are adjacentPick nodes from a tree to make the biggest total, but never pick a parent and its child together, by having every node report two numbers: with me and without me.Tree dynamic programming
- 30Print all K Sum paths in a Binary treeFind every straight downward chain of nodes in a tree whose numbers add up to k, using a notebook of running totals.Prefix sums with a hash map
- 31Find LCA in a Binary treeFind the closest shared grandparent of two people in a family tree by letting every branch report what it found.Depth first search
- 32Find distance between 2 nodes in a Binary treeCount the steps along the branches between two nodes of a tree, by finding where their paths up to the root meet.Lowest common ancestor
- 33Kth Ancestor of node in a Binary treeFind the great great grandparent k steps above a person in a family tree by counting down while the good news travels up.Depth first search
- 34Find all Duplicate subtrees in a Binary treeFind every branch shape that appears more than once in a tree, and report one copy of each.Hash map of subtree shapesMust do
- 35Tree Isomorphism ProblemDecide if one tree can be turned into another only by swapping the two children of some nodes, like turning mobiles around.Depth first search