Binary Tree

Definition and Terminology

Binary Tree Definition

Hierarchical data structure with nodes having at most two children. Each node contains data and references to left and right child nodes or null.

Node Components

Data: value stored in node. Left child: pointer/reference to left subtree. Right child: pointer/reference to right subtree. Parent: node above current node (optional).

Terminology

Root: topmost node with no parent. Leaf: node with no children. Internal node: node with at least one child. Subtree: tree rooted at any node.

Height and Depth

Height: longest path from node to leaf. Depth: distance from root to node. Level: nodes with same depth.

Types of Binary Trees

Full Binary Tree

Every node has 0 or 2 children. No nodes with only one child.

Complete Binary Tree

All levels fully filled except possibly last, filled left to right.

Perfect Binary Tree

All internal nodes have two children and all leaves at same level.

Degenerate (Pathological) Tree

Each parent node has only one child, resembling a linked list.

Balanced Binary Tree

Height difference between left and right subtrees of any node ≤ 1.

Properties of Binary Trees

Node Count Relations

Maximum nodes at level l: 2^l (l ≥ 0). Maximum nodes in tree of height h: 2^(h+1) - 1.

Height Bounds

Minimum height for n nodes: ⌊log2(n)⌋. Maximum height: n-1 (degenerate tree).

Number of Leaves

In a non-empty full binary tree, number of leaves = internal nodes + 1.

Path Length

Sum of depths of all nodes. Used for performance analysis.

Representation in Memory

Linked Representation

Nodes as objects with pointers to left and right children. Flexible, dynamic size.

Array Representation

Used for complete binary trees. Root at index 0 or 1, left child at 2i+1, right child at 2i+2 (0-based).

Comparison

Linked: efficient insertions/deletions. Array: efficient access, less memory overhead if complete.

Memory Overhead

Linked lists require pointer storage, arrays require contiguous memory.

Traversal Techniques

Preorder Traversal

Visit node, traverse left subtree, traverse right subtree. Used for copying trees.

Inorder Traversal

Traverse left subtree, visit node, traverse right subtree. Produces sorted sequence in BST.

Postorder Traversal

Traverse left subtree, traverse right subtree, visit node. Used for deleting trees.

Level Order Traversal

Visit nodes level by level using a queue. Breadth-first approach.

Traversal Algorithms

Both recursive and iterative implementations common. Stack or queue used in iterative.

Binary Search Tree (BST)

Definition

Binary tree where left subtree nodes ≤ root < right subtree nodes. Maintains sorted order.

Properties

Inorder traversal produces sorted sequence. Efficient search, insertion, deletion.

Search Operation

Start at root, compare key, recurse left or right based on comparison.

Insertion and Deletion

Insertion: find proper leaf position. Deletion: three cases - leaf, one child, two children (replace with inorder successor/predecessor).

Balanced Binary Trees

Need for Balance

Reduces height, improves performance of search, insert, delete to O(log n).

AVL Trees

Height-balanced: balance factor -1, 0, or 1. Rotations used to maintain balance.

Red-Black Trees

Color properties enforce balanced black height. Used in many libraries.

Splay Trees

Self-adjusting trees using rotations. Frequently accessed nodes move to root.

B-Trees (Brief)

Generalization of binary trees for disk storage, multi-way, balanced.

Basic Operations

Search

Locate node with given key. BST search average O(log n), worst O(n).

Insertion

Add new node preserving tree properties. May require rebalancing in balanced trees.

Deletion

Remove node, restructure tree to maintain properties. Cases depend on node children.

Traversal

Extract data in specific order for processing or visualization.

Height Calculation

Recursive method to determine height from root.

Applications

Data Sorting

Inorder traversal of BST yields sorted data. Basis for tree sort algorithms.

Expression Parsing

Expression trees represent arithmetic expressions. Traversals evaluate or output expressions.

Databases and Indexing

Balanced trees used in indexing for fast lookup and range queries.

Networking

Binary tries and prefix trees for IP routing and lookup.

Memory Management

Binary trees help manage free memory blocks via buddy systems.

Time and Space Complexity

Search

Average: O(log n) in balanced trees. Worst: O(n) in skewed trees.

Insertion

Same as search, plus rebalancing cost in balanced trees.

Deletion

Similar to insertion, depends on node position and rebalancing.

Traversal

O(n) for all traversal types since all nodes visited once.

Space Complexity

O(n) for storing n nodes plus overhead of pointers/references.

Examples and Illustrations

Simple Binary Tree

Root: 10, Left child: 5, Right child: 15. Demonstrates basic structure.

Full Binary Tree Example

Every node has 0 or 2 children. Visualizes complete and perfect trees.

BST Insertion Example

Insert 7 into BST with root 10 and left child 5. Resulting structure maintains order.

Traversal Output

Inorder: 5,7,10,15. Preorder: 10,5,7,15. Postorder: 7,5,15,10.

Balanced Tree Rotation

Illustrates single and double rotations to restore AVL balance.

Key Algorithms

Inorder Traversal (Recursive)

function inorder(node) if node != null inorder(node.left) visit(node) inorder(node.right)

BST Search

function searchBST(node, key) if node == null or node.key == key return node if key < node.key return searchBST(node.left, key) else return searchBST(node.right, key)

BST Insertion

function insertBST(node, key) if node == null return new Node(key) if key < node.key node.left = insertBST(node.left, key) else if key > node.key node.right = insertBST(node.right, key) return node

AVL Tree Rotation (Single Right)

function rightRotate(y) x = y.left T2 = x.right x.right = y y.left = T2 updateHeight(y) updateHeight(x) return x

Level Order Traversal

function levelOrder(root) queue = new Queue() queue.enqueue(root) while not queue.isEmpty() node = queue.dequeue() visit(node) if node.left != null queue.enqueue(node.left) if node.right != null queue.enqueue(node.right)

References

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, vol. 3, 2009, pp. 231-270.
• R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley, 2011, pp. 198-242.
• D.E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, 1997, pp. 328-370.
• S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Algorithms, McGraw-Hill, 2006, pp. 205-230.
• M.A. Weiss, Data Structures and Algorithm Analysis in C++, Pearson, 2013, pp. 150-190.