Binary Tree in Data Structure — Types and Implementation
A Binary Tree is a hierarchical data structure in which each node has at most two children, commonly referred to as the left child and the right child.
Types of Binary Trees
| Type | Description |
|---|---|
| Full Binary Tree | Every node has either 0 or 2 children. |
| Complete Binary Tree | All levels are completely filled except possibly the last, which is filled left to right. |
| Perfect Binary Tree | All internal nodes have two children and all leaves are at the same level. |
| Balanced Binary Tree | The height of the left and right subtrees of any node differ by at most one. |
| Degenerate (Skewed) Tree | Each parent node has only one child, resembling a linked list. |
Linked Node Implementation
class Node:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert_level_order(self, values):
# builds a complete binary tree from a list, left to right
if not values:
return
self.root = Node(values[0])
queue = [self.root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values):
node.left = Node(values[i]); queue.append(node.left); i += 1
if i < len(values):
node.right = Node(values[i]); queue.append(node.right); i += 1
Complexity
| Operation | Time |
|---|---|
| Search/Insert/Delete (unbalanced) | O(n) |
| Search/Insert/Delete (balanced) | O(log n) |
Applications
- Expression trees for evaluating mathematical expressions.
- Binary Search Trees for fast lookup.
- Huffman coding trees for data compression.
Ready to master Data Structures & Algorithms?
Learn DSA hands-on with mentor-led sessions, real interview practice, and placement support.