Welcome to the Binary Tree section of Javarena! This guide covers binary tree concepts, common operations, and interview problems with Java implementations to help you ace coding interviews.
- 🌟 What is a Binary Tree?
- 🌲 Types of Binary Trees
- 📏 Key Properties
- ⚙️ Common Operations
- 💻 Code Implementations
- 🧪 Practice Problems
- 📚 Resources
A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Binary trees are widely used in search algorithms, expression parsing, and hierarchical data representation.
1
/
2 3
/ \
4 5 6
- Root: Node 1 (topmost node)
- Parent: A node with children (e.g., 2 is the parent of 4 and 5)
- Leaf: Nodes with no children (e.g., 4, 5, 6)
- Full Binary Tree: Every node has either 0 or 2 children.
- Complete Binary Tree: All levels except possibly the last are fully filled, and the last level is filled from left to right.
- Perfect Binary Tree: All internal nodes have 2 children, and all leaf nodes are at the same level.
- Binary Search Tree (BST): Left subtree contains nodes with values less than the parent, and right subtree contains nodes with values greater than the parent.
- Balanced Binary Tree: Height of left and right subtrees of any node differs by at most 1 (e.g., AVL, Red-Black trees).
- Height: Number of edges on the longest path from root to leaf.
- Depth: Number of edges from the root to a specific node.
- Maximum nodes at level
L: 2^L nodes. - Maximum nodes in a tree of height
H:2^(H+1) - 1. - Minimum height for
Nnodes:floor(log2(N)).
| Operation | Time Complexity | Description |
|---|---|---|
| Inorder Traversal | O(n) | Left → Root → Right |
| Preorder Traversal | O(n) | Root → Left → Right |
| Postorder Traversal | O(n) | Left → Right → Root |
| Level Order Traversal | O(n) | Traverse level by level |
| Insertion (BST) | O(h) (h = height) | Insert a node in BST |
| Deletion (BST) | O(h) | Remove a node from BST |
| Search (BST) | O(h) | Find a node in BST |
Below is a Java implementation of a binary tree node and inorder traversal:
public class BinaryTree {
// Node class for binary tree
static class Node {
int val;
Node left;
Node right;
Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Inorder traversal: Left -> Root -> Right
public void inorderTraversal(Node root) {
if (root == null) return;
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
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);
root.right.right = new Node(6);
System.out.print("Inorder Traversal: ");
tree.inorderTraversal(root); // Output: 4 2 5 1 3 6
}
}