- Open Bookshelf Cover Page
- Preface
- Getting Started
- Introduction to Recursion
- Divide and Conquer Algorithms
- Dynamic Programming
-
Binary Trees
- Intro to Trees
- Binary Trees
- Types of Binary Trees
- Divide & Conquer in Tree Problems
- Practice: Binary Tree Height
- Tree Traversal: DFS and BFS
- Practice: Preorder Traversal
- Practice: Inorder Traversal
- Practice: Postorder Traversal
- Practice: Level Order Traversal
- Binary Search Tree
- Practice: Find Node in a BST
- Graphs
- Backtracking
- Conclusion
- Share on
Types of Binary Trees
Binary trees come in various forms, each with specific properties that make them suitable for different computational scenarios. This lesson will explore the types of binary trees, namely Full Binary Trees, Complete Binary Trees, Perfect Binary Trees, and Balanced Binary Trees.
Full Binary Tree
A Full Binary Tree is a type of binary tree where every node has either zero or two children. In other words, no node has only one child.
Complete Binary Tree
In a complete binary tree, all levels are completely filled with nodes, except possibly for the last level. On the last level, nodes are filled from left to right.
Perfect Binary Tree
A perfect binary tree is a special case in which it is both a full and complete binary tree. It's the most symmetrical type of binary tree, where all internal nodes have two children, and all leaf nodes are at the same level (depth).
Interesting Properties of Perfect Binary Trees:
- The total number of nodes doubles as we move down each level. You can see in the image that the first level contains one node, the second level contains two nodes, and the third level contains four nodes. If we had another level, it would contain eight nodes, and so on. In other words, this means that the height of the tree grows logarithmically.
- The number of nodes at the last level equals the sum of nodes at all other levels plus one.
Balanced Binary Tree
A balanced binary tree (or height-balanced binary tree) is a binary tree where the height of the left and right subtrees of any node differs by at most one.
In the image below, the height of the left side from the root node is two, and the height of the right side is one, so the tree is balanced as the heights don't differ by more than one.
If we added another node on the left side, the tree would become imbalanced as the height of the left side, looking from the root node, would become three, and the height of the right side would still be one.
