Binary Tree
Introduction
Have you ever wondered how data structures can be used to organize information into hierarchies? A binary tree is one type of structure that enables us to do just that! This article will explore the concept and implications of implementing a binary tree in data structure, including its strengths and weaknesses compared to other approaches. You’ll also come away with knowledge about common algorithms associated with binary trees, along with methods for visualizing them. Whether you're already familiar with this subject or just starting out learning about computer science, this article should have something exciting for everyone so let's get started!
What is a binary tree in data structure
In data structure, a binary tree is a type of tree data structure that consists of nodes, which are connected by edges. At the top, there is a root node, and every node can have at most two children, that is, a right and left child. Binary trees are often used for searching and sorting purposes, and they offer a convenient way to store data in an organized manner. Their defining characteristic of having only two children means that they can be easily traversed unlike other tree structures, and this makes them very efficient in searching for specific data within a large set of data. Overall, binary tree in data structure is an essential topic for any student of computer science who wants to gain a deeper understanding of data structures and algorithms.
Binary tree representation in data structure
Binary trees are an essential component of data structures. They are powerful tools that can be used for sorting, searching, and navigating through data. In a binary tree, each node can have at most two children or branches, which are called the left child and the right child. The tree is said to be balanced if the left and right subtrees are equal in size. Binary tree representation in data structure is particularly useful in programming algorithms, as it allows for efficient traversal and search operations. Whether the user constructing a new program or working with existing code, understanding binary tree representation is a crucial step in mastering data structures. A Binary tree is represented by a pointer to the topmost node of the tree. If the tree is empty, then the value of the root is NULL. Each node of a Binary Tree contains the following parts:
- Data
- Pointer to the left child
- Pointer to the right child
Binary tree terminology in data structure
- Node: In a binary tree, a node refers to a data element that is stored in the tree. Each node in a binary tree can have at most two child nodes, referred to as the left child and the right child. Each node contains a key or a value, which is used to search for and access the node in the tree. In addition to the key or value, a node can also store other information, such as pointers to its child nodes, parent node, or any other relevant data.
- Root: In a binary tree, a root is the topmost node of the tree. It is the starting point of the tree from which all other nodes branch out. Every binary tree has exactly one root node, which has no parent node. The root node serves as the anchor point for the entire tree and is responsible for keeping the tree structure organized.
- Parent: In a binary tree, a parent is a node that has at least one child node. Specifically, if a node has one or two child nodes, the node is considered a parent. The child nodes are located directly beneath the parent node in the tree structure.
- Child: In a binary tree, a child refers to a node that is directly connected to another node called its parent. Specifically, in a binary tree, each node can have at most two children, one on its left and one on its right. If a node has a child, it means that there is a link from the parent node to the child node in the tree structure.
- Leaf Node: A leaf node in a binary tree is a node that does not have any children, that is, it is a terminal node in the tree. In other words, a leaf node is a node that has no left or right child node. It is also called a "terminal node" or a "leaf" of the tree.
- Internal Node: In a binary tree, an internal node is a node that has at least one child. Specifically, it is a node that is not a leaf node, which means it has at least one child node below it.
- Depth of a Tree: The depth of a tree in a binary tree refers to the length of the longest path from the root node of the tree to any leaf node in the tree. In other words, it is the number of edges in the longest path from the root to a leaf node. The depth of a binary tree is used to measure the height or the maximum depth of the binary tree. A binary tree with only one node has a depth of 0, while a binary tree with two or more nodes has a depth of at least 1.
- Height of a Tree: The height of a binary tree is the length of the longest path from the root to any leaf node in the tree. In other words, it is the number of edges on the longest path from the root to a leaf node. The height of a binary tree with only one node (the root) is 0. If the tree has no nodes (i.e., it is an empty tree), its height is -1.
Types of binary tree in data structure
There are five types of binary tree in data structure:
Full/ proper/ strict Binary tree- A full binary tree, also known as a proper binary tree or a strictly binary tree, is a type of binary tree in which every node has either zero or two children. In a full binary tree, each node can have either zero or two children, but not one. Additionally, all leaf nodes are at the same level. In other words, the tree is "full" because every level is completely filled with nodes, except for possibly the last level, which may not be full.
Properties of a full binary tree
- The maximum number of nodes at a given level is 2^(k-1), where k is the level number.
- The maximum number of nodes in a full binary tree with height h is 2^h - 1.
- If a full binary tree has n nodes, then its height is log2(n+1).
Complete Binary tree
A complete binary tree is a binary tree in which all levels except possibly the last level are completely filled, and all nodes are as far left as possible. In other words, a complete binary tree is a binary tree where every level is completely filled, except possibly for the last level, which is filled from left to right.
Properties of complete binary tree
The maximum number of nodes: A complete binary tree with height h has the maximum number of possible nodes when all levels are completely filled, which is 2^(h+1) - 1 node.
The minimum number of nodes: A complete binary tree with height h has minimum possible nodes when the last level is partially filled and all the nodes are pushed to the left side of the tree, which is 2^h nodes.
Height: The height of a complete binary tree with n nodes is log2(n+1) - 1.
Parent-child relationship: The parent of the node at index i in a complete binary tree is at index floor(i/2), and its children are at indices 2i and 2i+1.
Level order traversal: In a complete binary tree, a level order traversal visits nodes from left to right, starting from the root node.
Array representation: A complete binary tree can be represented using an array, where the parent of the node at index i is at index floor(i/2), and its children are at indices 2i and 2i+1.
Balanced: A complete binary tree is always balanced, meaning the height of the left and right subtrees of any node differ by at most 1.
Perfect Binary tree
A perfect binary tree is a type of binary tree in which all levels are completely filled with nodes, and all leaf nodes are at the same level. In other words, a perfect binary tree is a binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same depth or level.
Properties of perfect binary tree
All levels of the tree are completely filled, except possibly the last level, which is filled from left to right.
- The number of nodes in a perfect binary tree can be calculated using the formula 2^h - 1, where h is the height or depth of the tree.
- The height of a perfect binary tree can be calculated using the formula log2(n + 1) - 1, where n is the number of nodes in the tree.
- The root node of a perfect binary tree is always at level 0.
- The number of nodes in the last level of a perfect binary tree is equal to 2^(h-1), where h is the height of the tree.
- The maximum number of nodes at any level of a perfect binary tree is 2^k, where k is the level number.
- The minimum height of a perfect binary tree with n nodes is floor(log2(n)).
Degenerate Binary tree
A degenerate binary tree, also known as a pathological tree, is a special type of binary tree where each parent node has only one child node. In other words, it is a tree in which all the internal nodes have a degree of 1, and only the leaf nodes have a degree of 0.
Properties of Degenerate binary tree
- Height: The height of a degenerate binary tree is equal to the number of nodes in the tree, as each node only has one child. Thus, the height of a degenerate binary tree is equal to the number of edges in the longest path from the root to a leaf node.
- Balancedness: A degenerate binary tree is always unbalanced, as one side of the tree has all the nodes and the other side is empty.
- Traversal: Since there is only one child per node, a traversal of a degenerate binary tree can be performed in linear time using either an in-order traversal or a pre-order traversal.
- Space complexity: The space complexity of a degenerate binary tree is O(n), where n is the number of nodes in the tree since each node only has one child.
- Operations: Because of its unbalanced nature, operations on a degenerate binary tree can be slow, as they may require traversing the entire height of the tree. For example, searching for a particular node can take O(n) time in the worst case.
Balanced Binary tree
A balanced binary tree is a type of binary tree in which the difference in height between the left and right subtrees of any node is at most one. In other words, a balanced binary tree is a binary tree in which the depth of all the leaf nodes is roughly the same. Balanced binary trees have several important properties that make them useful in computer science and programming.
Properties of Balanced binary tree
- Height: The height of a balanced binary tree with n nodes is O(log n). This is in contrast to an unbalanced binary tree, where the height could be as large as n.
- Search time: The time required to search for a node in a balanced binary tree is O(log n), which is much faster than in an unbalanced binary tree.
- Insertion and deletion time: The time required to insert or delete a node in a balanced binary tree is also O(log n). This is because the tree needs to be rebalanced after the insertion or deletion, but the rebalancing operations take O(log n) time.
- Space efficiency: A balanced binary tree uses space efficiently because the height is O(log n). This means that the number of nodes at each level of the tree is roughly the same, and there are not many levels in the tree.
AVL trees and Red-Black trees
AVL trees and Red-Black trees are two popular types of balanced binary trees. Both of these trees ensure that the heights of the left and right subtrees of every node differ by at most one. The difference between AVL trees and Red-Black trees is in the way they are rebalanced. AVL trees are more balanced than Red-Black trees, but they require more frequent rebalancing. Red-Black trees are less balanced than AVL trees, but they require less frequent rebalancing.
Applications
Balanced binary trees are commonly used in computer science applications that require efficient searching, insertion, and deletion operations. Examples include databases, search engines, and compilers
Basic Operations On Binary Tree
Insertion
To insert a new node into a binary tree, the user needs to find the appropriate location in the tree. If the new node is greater than the current node, it should be inserted to the right of the current node. If it is less than the current node, it should be inserted to the left of the current node. If there is already a node at that location, will need to traverse further down the tree until they find an empty location where the new node can be inserted.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def createNode(data):
return Node(data)
def insert(root, data):
if root is None:
root = createNode(data)
return root
if data < root.data:
root.left = insert(root.left, data)
else:
root.right = insert(root.right, data)
return root
def inorder(root):
if root is not None:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
root = None
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)
print("Inorder traversal of the binary tree is: ")
inorder(root)
public class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
public static Node createNode(int data) {
return new Node(data);
}
public static Node insert(Node root, int data) {
if (root == null) {
root = createNode(data);
return root;
}
if (data < root.data) {
root.left = insert(root.left, data);
}
else {
root.right = insert(root.right, data);
}
return root;
}
public static void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
public static void main(String[] args) {
Node root = null;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
System.out.print("Inorder traversal of the binary tree is: ");
inorder(root);
}
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* createNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void insert(Node*& root, int data) {
if (root == NULL) {
root = createNode(data);
return;
}
if (data < root->data) {
insert(root->left, data);
}
else {
insert(root->right, data);
}
}
void inorder(Node* root) {
if (root == NULL) {
return;
}
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main() {
Node* root = NULL;
insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
cout << "Inorder traversal of the binary tree is: ";
inorder(root);
return 0;
}
Output
Inorder traversal of the binary tree is: 20 30 40 50 60 70 80
Deletion
To delete a node from a binary tree, the user needs to first find the node that needs to be deleted. Once the developer has found the node, there are three possible cases to consider: (1) the node has no children, (2) the node has one child, or (3) the node has two children. If the node has no children, simply remove the node from the tree. If the node has one child, remove the node and connect its child to its parent. If the node has two children, find the node with the smallest value in the right subtree (or the node with the largest value in the left subtree), swap it with the node to be deleted, and then delete the node with the smaller value.
# Definition for a binary tree node
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# Function to delete a binary tree
def deleteTree(root):
if root == None:
return
# Delete the left and right subtrees
deleteTree(root.left)
deleteTree(root.right)
# Delete the root node
print("Deleting node with value", root.val)
del root
# Create a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# Delete the binary tree
deleteTree(root)
// Definition for a binary tree node
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
left = null;
right = null;
}
}
// Function to delete a binary tree
public static void deleteTree(TreeNode root) {
if (root == null) return;
// Delete the left and right subtrees
deleteTree(root.left);
deleteTree(root.right);
// Delete the root node
System.out.println("Deleting node with value " + root.val);
root = null;
}
public static void main(String[] args) {
// Create a sample binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// Delete the binary tree
deleteTree(root);
}
#include <iostream>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// Function to delete a binary tree
void deleteTree(TreeNode* root) {
if (root == NULL) return;
// Delete the left and right subtrees
deleteTree(root->left);
deleteTree(root->right);
// Delete the root node
cout << "Deleting node with value " << root->val << endl;
delete root;
}
int main() {
// Create a sample binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// Delete the binary tree
deleteTree(root);
return 0;
}
Output
Deleting node with value 4
Deleting node with value 5
Deleting node with value 2
Deleting node with value 3
Deleting node with value 1
Traversal
There are three common ways to traverse a binary tree: in order, preorder, and postorder. In inorder traversal, the user visits the left subtree, then the current node, and then the right subtree. In preorder traversal, the user visits the current node, then the left subtree, and then the right subtree. In postorder traversal, they visit the left subtree, then the right subtree, and then the current node.
C++
# Define the node class for binary tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to traverse the binary tree in pre-order and print the nodes
def preOrder(root):
if root is None:
return
print(root.data, end=' ')
preOrder(root.left)
preOrder(root.right)
# Function to traverse the binary tree in in-order and print the nodes
def inOrder(root):
if root is None:
return
inOrder(root.left)
print(root.data, end=' ')
inOrder(root.right)
# Function to traverse the binary tree in post-order and print the nodes
def postOrder(root):
if root is None:
return
postOrder(root.left)
postOrder(root.right)
print(root.data, end=' ')
# Create the binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# Traverse the binary tree in pre-order and print the nodes
print("Pre-order traversal:", end=' ')
preOrder(root)
print()
# Traverse the binary tree in in-order and print the nodes
print("In-order traversal:", end=' ')
inOrder(root)
print()
# Traverse the binary tree in post-order and print the nodes
print("Post-order traversal:", end=' ')
postOrder(root)
print()
public class Main {
// Define the node class for binary tree
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Function to traverse the binary tree in pre-order and print the nodes
static void preOrder(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
// Function to traverse the binary tree in in-order and print the nodes
static void inOrder(Node root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
// Function to traverse the binary tree in post-order and print the nodes
static void postOrder(Node root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
// Create the binary tree
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
// Traverse the binary tree in pre-order and print the nodes
System.out.print("Pre-order traversal: ");
preOrder(root);
System.out.println();
// Traverse the binary tree in in-order and print the nodes
System.out.print("In-order traversal: ");
inOrder(root);
System.out.println();
// Traverse the binary tree in post-order and print the nodes
System.out.print("Post-order traversal: ");
postOrder(root);
System.out.println();
}
#include <iostream>
using namespace std;
// Define the node struct for binary tree
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new node with given data
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = nullptr;
node->right = nullptr;
return node;
}
// Function to traverse the binary tree in pre-order and print the nodes
void preOrder(Node* root) {
if (root == nullptr) {
return;
}
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
// Function to traverse the binary tree in in-order and print the nodes
void inOrder(Node* root) {
if (root == nullptr) {
return;
}
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}
// Function to traverse the binary tree in post-order and print the nodes
void postOrder(Node* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
int main() {
// Create the binary tree
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Traverse the binary tree in pre-order and print the nodes
cout << "Pre-order traversal: ";
preOrder(root);
cout << endl;
// Traverse the binary tree in in-order and print the nodes
cout << "In-order traversal: ";
inOrder(root);
cout << endl;
// Traverse the binary tree in post-order and print the nodes
cout << "Post-order traversal: ";
postOrder(root);
cout << endl;
return 0;
}
Output
Pre-order traversal: 1 2 4 5 3
In-order traversal: 4 2 5 1 3
Post-order traversal: 4 5 2 3 1
Search
To search for a specific value in a binary tree, the user can start at the root node and compare the value they are searching for with the value of the current node. If the value they are searching for is less than the current node, move to the left child. If it is greater than the current node, move to the right child. Repeat this process until they find the node with the value that are searching for, or until they reach a leaf node which means the value is not in the tree.
# Define the node class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to insert a new node into the binary tree
def insert_node(node, data):
if node is None:
return Node(data)
if data < node.data:
node.left = insert_node(node.left, data)
elif data > node.data:
node.right = insert_node(node.right, data)
return node
# Function to search for a value in the binary tree
def search(node, data):
if node is None:
return False
if node.data == data:
return True
if data < node.data:
return search(node.left, data)
else:
return search(node.right, data)
# Main function
if __name__ == '__main__':
# Create the binary tree
root = None
root = insert_node(root, 5)
insert_node(root, 3)
insert_node(root, 7)
insert_node(root, 1)
insert_node(root, 9)
# Search for values in the binary tree
print("Searching for 7:", "Found" if search(root, 7) else "Not Found")
print("Searching for 4:", "Found" if search(root, 4) else "Not Found")
public class Main {
// Define the node structure
static class Node {
int data;
Node left;
Node right;
}
// Function to create a new node
static Node newNode(int data) {
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
// Function to insert a new node into the binary tree
static Node insertNode(Node node, int data) {
if (node == null) {
return newNode(data);
}
if (data < node.data) {
node.left = insertNode(node.left, data);
} else if (data > node.data) {
node.right = insertNode(node.right, data);
}
return node;
}
// Function to search for a value in the binary tree
static boolean search(Node node, int data) {
if (node == null) {
return false;
}
if (node.data == data) {
return true;
}
if (data < node.data) {
return search(node.left, data);
} else {
return search(node.right, data);
}
}
// Main function
public static void main(String[] args) {
// Create the binary tree
Node root = null;
root = insertNode(root, 5);
insertNode(root, 3);
insertNode(root, 7);
insertNode(root, 1);
insertNode(root, 9);
// Search for values in the binary tree
System.out.println("Searching for 7: " + (search(root, 7) ? "Found" : "Not Found"));
System.out.println("Searching for 4: " + (search(root, 4) ? "Found" : "Not Found"));
}
}
#include <iostream>
using namespace std;
// Define the node structure
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new node
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = nullptr;
node->right = nullptr;
return node;
}
// Function to insert a new node into the binary tree
Node* insertNode(Node* node, int data) {
if (node == nullptr) {
return newNode(data);
}
if (data < node->data) {
node->left = insertNode(node->left, data);
}
else if (data > node->data) {
node->right = insertNode(node->right, data);
}
return node;
}
// Function to search for a value in the binary tree
bool search(Node* node, int data) {
if (node == nullptr) {
return false;
}
if (node->data == data) {
return true;
}
if (data < node->data) {
return search(node->left, data);
}
else {
return search(node->right, data);
}
}
// Main function
int main() {
// Create the binary tree
Node* root = nullptr;
root = insertNode(root, 5);
insertNode(root, 3);
insertNode(root, 7);
insertNode(root, 1);
insertNode(root, 9);
// Search for values in the binary tree
cout << "Searching for 7: " << (search(root, 7) ? "Found" : "Not Found") << endl;
cout << "Searching for 4: " << (search(root, 4) ? "Found" : "Not Found") << endl;
return 0;
}
Output
Searching for 7: Found
Searching for 4: Not Found
Auxiliary Operation On Binary Tree
- Height calculation: This operation determines the height of a binary tree, which is the maximum number of edges from the root to a leaf node.
- Diameter calculation: This operation determines the longest path between any two leaf nodes in a binary tree.
- Level order traversal: This operation visits all nodes in a binary tree in level order, from top to bottom and from left to right.
- Mirror image creation: This operation creates a mirror image of a binary tree by swapping the left and right subtrees of each node.
- Inorder successor: This operation finds the inorder successor of a given node in a binary tree, which is the node with the smallest key greater than the given node's key.
- LCA (Lowest Common Ancestor): This operation finds the lowest common ancestor of two nodes in a binary tree, which is the deepest node that has both nodes as descendants.
Summary
Overall, the binary tree data structure is both an efficient and invasive tool. It provides a basic framework for developers to explore more sophisticated structures without having to do the work from scratch. By understanding its core principles, developers can quickly put together any type of tree data structure that suits their needs. And with its powerful capabilities, developers can easily create powerful software that surpasses the limitations of existing frameworks. The potential for what can be accomplished through binary tree data structure is vast– it gives us the power to make huge leaps forward in terms of how software applications are developed and deployed in the future. As a call to action, take the time to learn about binary tree in data structure so you can take advantage of this powerful tool and use it effectively on your next project!
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
