Algorithm
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. The topmost node in a binary tree is called the root. Nodes with no children are called leaves. Each node in a binary tree contains a value, and the structure of the tree helps organize and search for values efficiently.
Here are some key terms related to binary trees:
-
Root: The topmost node in a tree, from which all other nodes are descended.
-
Node: Each element in a tree that contains a value and references to its left and right children.
-
Leaf: A node with no children, i.e., a node that is at the end of a branch.
-
Parent: A node in a tree that has one or more children.
-
Child: A node in a tree that has a parent.
-
Siblings: Nodes with the same parent.
-
Depth: The level or distance of a node from the root. The root node is at depth 0.
-
Height: The length of the longest path from a node to a leaf. The height of a tree is the height of its root.
Binary trees are commonly used in computer science for various purposes, including binary search trees (BSTs) where the structure of the tree allows for efficient searching, insertion, and deletion operations. Additionally, binary trees are used in expression trees, Huffman trees, and various other applications.
Code Examples
#1 Binary Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = self.insert(root.right, key)
else:
root.left = self.insert(root.left, key)
return root
def inorder_traversal(self, root):
result = []
if root:
result = self.inorder_traversal(root.left)
result.append(root.val)
result = result + self.inorder_traversal(root.right)
return result
# Example usage:
if __name__ == "__main__":
tree = BinaryTree()
root = None
keys = [8, 3, 10, 1, 6, 9, 12]
for key in keys:
root = tree.insert(root, key)
print("Inorder Traversal:", tree.inorder_traversal(root))
#2 Binary Tree implement in Java
Code -
Java Programming
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
public BinaryTree() {
root = null;
}
// Method to insert a new node with the given data
public void insert(int data) {
root = insertRec(root, data);
}
// Recursive helper method to insert a new node with the given data
private Node insertRec(Node root, int data) {
// If the tree is empty, create a new node
if (root == null) {
root = new Node(data);
return root;
}
// Otherwise, recur down the tree
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
// Return the unchanged node pointer
return root;
}
// Method to perform an inorder traversal of the tree
public void inorder() {
inorderRec(root);
}
// Recursive helper method for inorder traversal
private void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// Insert some nodes into the tree
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Perform inorder traversal to display the elements
System.out.println("Inorder traversal of the binary tree:");
tree.inorder();
}
}
#3 Binary Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new node with the given data
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a new node with the given data into the binary tree
struct TreeNode* insert(struct TreeNode* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// Function to perform an in-order traversal of the binary tree
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Function to perform a pre-order traversal of the binary tree
void preOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// Function to perform a post-order traversal of the binary tree
void postOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// Driver program to test the binary tree implementation
int main() {
struct TreeNode* root = NULL;
// Insert nodes into the binary tree
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Perform different traversals
printf("In-order traversal: ");
inOrderTraversal(root);
printf("\n");
printf("Pre-order traversal: ");
preOrderTraversal(root);
printf("\n");
printf("Post-order traversal: ");
postOrderTraversal(root);
printf("\n");
return 0;
}
#4 Binary Tree implement in C++
Code -
C++ Programming
#include <iostream>
using namespace std;
// Define a node for the binary tree
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
// Constructor
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
// Class for the Binary Tree
class BinaryTree {
private:
TreeNode* root;
// Helper function to insert a value into the tree
TreeNode* insert(TreeNode* node, int value) {
if (node == nullptr) {
return new TreeNode(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else {
node->right = insert(node->right, value);
}
return node;
}
// Helper function to perform an inorder traversal of the tree
void inorderTraversal(TreeNode* node) {
if (node != nullptr) {
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
}
public:
// Constructor
BinaryTree() : root(nullptr) {}
// Public method to insert a value into the tree
void insert(int value) {
root = insert(root, value);
}
// Public method to perform an inorder traversal of the tree
void inorderTraversal() {
inorderTraversal(root);
cout << endl;
}
};
// Example usage
int main() {
BinaryTree tree;
// Insert values into the tree
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Perform an inorder traversal
cout << "Inorder Traversal: ";
tree.inorderTraversal();
return 0;
}
Demonstration
Binary Tree-DevsEnv