Binary Tree
A binary tree is a tree where each node has at most two children, typically called left and right. Binary trees are the foundation for many advanced structures like binary search trees and heaps.
Types of binary trees:
- Full binary tree – every node has 0 or 2 children.
- Complete binary tree – all levels filled except last, and nodes are as far left as possible.
- Perfect binary tree – all internal nodes have 2 children and all leaves are at same level.
- Balanced binary tree – height difference between left and right subtrees is at most 1 for every node.
Basic operations: insertion, traversal, search. Implementation with Java:
public class BinaryTree {
TreeNode root;
public void insert(int val) {
root = insertRec(root, val);
}
private TreeNode insertRec(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insertRec(root.left, val);
else if (val > root.val) root.right = insertRec(root.right, val);
return root;
}
}
Two Minute Drill
- Binary tree nodes have left and right children.
- Variants: full, complete, perfect, balanced.
- Common operations: insertion (O(log n) for BST, but O(n) for arbitrary), traversal.
- Foundation for BST, heap, AVL, etc.
Need more clarification?
Drop us an email at career@quipoinfotech.com