Binary Trees - potatoscript/dsa GitHub Wiki
🧩 What is a Binary Tree?
A binary tree is a special type of tree where each node has at most two children. These children are usually referred to as the left child and the right child. Imagine a family where each person can have no more than two kids—a left child and a right child. This makes it easier to organize and search for information!
📚 Structure of a Binary Tree
A binary tree consists of:
- Root: The topmost node of the tree.
- Node: A node contains a value and has left and right children (or no children).
- Left Child: The left child of a node.
- Right Child: The right child of a node.
- Leaf: A node that does not have any children.
🔍 Simple Visual Example:
1
/ \
2 3
/ \
4 5
- Root = 1
- Left Child of 1 = 2
- Right Child of 1 = 3
- Children of 2 = 4 and 5
- Leaves = 3, 4, 5 (since these nodes have no children)
🧩 Real-Life Analogy: Family Tree
Let’s use a family tree analogy for a binary tree.
- Imagine the root of the tree is the grandparent.
- The left child of the grandparent is child 1, and the right child is child 2.
- Child 1 can also have its own children, but Child 2 can also have children too, and this structure repeats.
Each family member can have no more than two children, which is exactly how binary trees work! 📜👪
🧃 Key Operations on Binary Trees
1. Insertion
Inserting a node in a binary tree means adding a new node to the tree. The insertion process depends on where you insert the node (left or right) based on the binary tree's structure or specific rule (like binary search trees, which we'll discuss later).
2. Traversal
Traversal means visiting all the nodes in the tree. There are three main ways to traverse a binary tree:
- Pre-order traversal: Visit the root, then the left child, then the right child.
- In-order traversal: Visit the left child, then the root, then the right child.
- Post-order traversal: Visit the left child, then the right child, then the root.
3. Searching
Searching involves finding a specific node or value in the tree. It can be done by traversing the tree.
4. Deletion
In deletion, we remove a node from the tree. We must consider three cases:
- The node has no children (just delete it).
- The node has one child (remove the node and connect the child).
- The node has two children (find the smallest node in the right subtree or the largest node in the left subtree and replace the node with that).
🧩 Visualizing Binary Tree Operations
📚 C# Code Example for Binary Tree Node
In C#, we can create a Binary Tree Node class. Here’s how it looks:
public class BinaryTreeNode
{
public int Value;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public BinaryTreeNode(int value)
{
Value = value;
Left = null;
Right = null;
}
}
This class will represent a node in the binary tree, where each node has:
- A Value (the data stored in the node),
- A Left pointer (to its left child),
- A Right pointer (to its right child).
📚 Binary Tree Insertion (Adding Nodes)
Let's see how to insert nodes into a binary tree. We’ll insert a new node by simply adding it as the left or right child of an existing node.
public class BinaryTree
{
public BinaryTreeNode Root;
// Constructor
public BinaryTree()
{
Root = null;
}
// Method to insert a node into the tree
public void Insert(int value)
{
BinaryTreeNode newNode = new BinaryTreeNode(value);
if (Root == null)
{
Root = newNode;
}
else
{
Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
queue.Enqueue(Root);
while (queue.Count > 0)
{
BinaryTreeNode current = queue.Dequeue();
if (current.Left == null)
{
current.Left = newNode;
break;
}
else
{
queue.Enqueue(current.Left);
}
if (current.Right == null)
{
current.Right = newNode;
break;
}
else
{
queue.Enqueue(current.Right);
}
}
}
}
}
In this code, we:
- Create a new node with the given value.
- If the tree is empty, the new node becomes the root.
- Otherwise, we insert the new node at the first available spot in the tree (either the left or right child of the first empty node).
📚 Traversal Examples
Here’s how we can implement Pre-order, In-order, and Post-order traversals.
Pre-order Traversal (Root, Left, Right)
public void PreOrderTraversal(BinaryTreeNode node)
{
if (node == null) return;
Console.WriteLine(node.Value);
PreOrderTraversal(node.Left);
PreOrderTraversal(node.Right);
}
In-order Traversal (Left, Root, Right)
public void InOrderTraversal(BinaryTreeNode node)
{
if (node == null) return;
InOrderTraversal(node.Left);
Console.WriteLine(node.Value);
InOrderTraversal(node.Right);
}
Post-order Traversal (Left, Right, Root)
public void PostOrderTraversal(BinaryTreeNode node)
{
if (node == null) return;
PostOrderTraversal(node.Left);
PostOrderTraversal(node.Right);
Console.WriteLine(node.Value);
}
📚 Search Example
Here’s how we search for a node in a binary tree:
public BinaryTreeNode Search(BinaryTreeNode node, int value)
{
if (node == null || node.Value == value)
return node;
if (value < node.Value)
return Search(node.Left, value);
return Search(node.Right, value);
}
This search function checks:
- If the node is null or if the node’s value matches the searched value.
- It then recursively searches the left or right subtree based on whether the value is smaller or larger than the current node.
🧩 Key Terms in Binary Trees:
- Leaf Node: A node that has no children.
- Root: The topmost node of the tree.
- Height of the Tree: The number of edges from the root to the deepest leaf.
- Depth of a Node: The number of edges from the root to the node.
🧠 Time Complexity (Big O)
- Search, Insert, and Delete (on average): O(log n) for balanced binary trees.
- Traversal (Pre-order, In-order, Post-order): O(n), because each node is visited once.
🧩 Practical Applications of Binary Trees:
- Binary Search Trees (BST): Used to efficiently search for, insert, and delete nodes.
- Expression Trees: Represent mathematical expressions (binary operations).
- Huffman Encoding Trees: Used in data compression algorithms.