DSA Binary Trees

A binary tree restricts every node to at most two children, commonly labeled left and right, which enables efficient search, sort, and balancing algorithms.

What Is a Binary Tree?

A binary tree is a tree in which every node has at most two children, conventionally called the left child and the right child. This simple constraint is what makes binary trees so useful: it bounds how branching can occur, which is the foundation for binary search trees, heaps, and expression trees.

Types of Binary Trees

  • Full binary tree - every node has either 0 or 2 children, never exactly 1
  • Complete binary tree - every level is fully filled except possibly the last, which fills left to right
  • Perfect binary tree - every internal node has exactly 2 children and every leaf sits at the same depth
  • Balanced binary tree - the height of the left and right subtrees of any node differs by at most a small constant
  • Degenerate (skewed) tree - every node has only one child, so the tree behaves like a linked list

Example

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = BinaryNode(8)
root.left = BinaryNode(3)
root.right = BinaryNode(10)
root.left.left = BinaryNode(1)
root.left.right = BinaryNode(6)

print(root.value)              # 8
print(root.left.value)         # 3
print(root.left.right.value)   # 6

The Binary Search Tree (BST) Property

A binary search tree adds one rule on top of the basic binary tree: for every node, every value in its left subtree is smaller than the node's value, and every value in its right subtree is larger. This ordering means you can search, insert, or delete a value by comparing it against each node and immediately discarding half of the remaining tree - the same idea behind binary search on a sorted array.

Example

def insert(node, value):
    if node is None:
        return BinaryNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node

bst_root = None
for number in [8, 3, 10, 1, 6, 14, 4, 7]:
    bst_root = insert(bst_root, number)

print(bst_root.value)        # 8
print(bst_root.left.value)   # 3

Example

def search(node, target):
    if node is None:
        return False
    if node.value == target:
        return True
    if target < node.value:
        return search(node.left, target)
    return search(node.right, target)

print(search(bst_root, 7))    # True
print(search(bst_root, 20))   # False
OperationBalanced BSTSkewed BST
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
Note: Inserting sorted or nearly-sorted data straight into a plain BST tends to produce a skewed, list-like tree. Self-balancing variants such as AVL trees and red-black trees fix this by rotating nodes to keep the height close to log(n).
Note: Recursive insert and search functions like the ones above assume no duplicate values are inserted; you must decide up front how duplicates should be handled (ignored, allowed on one side, or counted) or the tree's ordering guarantee can break down.

Exercise: DSA Binary Trees

What defines a binary tree?

Keep Going

Data Structures Interview QuestionsPractice real questions asked for Data StructuresSoftware Engineer SalarySee what Software Engineer roles pay in the marketAuto Apply for JobsApply to open roles related to Data Structures and tweak your resume