Skip to content
Notes on Binary Tree
- Tree with max 2 children in each node.
- The maximum number of nodes at level ‘l’ of a binary tree is 2^(l-1). Level of root is 1.
- Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1
- Types of binary tree
- Full binary tree – binary tree with all intermediate nodes with 0 or 2 nodes.
- Perfect binary tree – full binary tree and all leaf nodes at the same level.
- Complete binary tree – binary tree that has all intermediate nodes with 2 children except last level where keys are aligned to left.
- Degenerate tree – all nodes have just one child.
- Balanced tree – binary tree where the height is o(log n) where n is the number of nodes.
- Labeled trees & unlabeled trees – In case of labeled tree, every node has a label which make its position unique.
- Height of the tree – Longest path from the root the leaves.
- Diameter of the tree – Diameter of a tree is the number of nodes on the longest path between 2 leaves in the tree.
- Width of the tree – Number of nodes in the level which has got the max number of nodes among levels. Can be found using level order.
- Traversals
- Depth first traversal
- InOrder (Left, Root, Right)
- PreOrder (Root, Left, RIght)
- PostOrder (Left, Right, Root)
- Breadth first traversal
- Level order traversal – Going to every level and print all the nodes in it.
- Depth first traversal – It’s usually done with stack or recursion. It’s possible to traverse without stack/recursion through threaded binary tree approach.
- Constructing tree from the traversal methods – If one of the traversals is InOrder, we could reconstruct the tree. Example of constructing the tree using the InOrder and PreOrder information
- One example from web here.
- Tips on solving problems tied to binary tree
- Rely on recursion.
- Pass down the variable or Leverage return value.
- Process the current node and set up default condition when root is null.
Binary Tree – Problems
