Topic 55 of 78
Binary Trees
Overview
Unlike Arrays or Linked Lists which are linear (one element simply follows another), a Tree is a hierarchical data structure. A Binary Tree is a tree where every Node can have a maximum of TWO children (a Left child and a Right child). This hierarchy naturally mimics real-world data like organizational charts, file systems, or DOM trees in web browsers. Binary Trees form the foundation for highly optimized searching and routing algorithms.
Syntax
Every tree starts at the `root`. Nodes with no children are called 'Leaves'. The distance from the root to the deepest leaf is the 'Height' of the tree.
Defining a Binary Tree Node
java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
TreeNode root; // The very top of the tree
public void buildBasicTree() {
root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
// 1
// / \
// 2 3
}
}Common Pitfalls
- Stack Overflow Errors. Because trees are naturally recursive structures, trying to traverse an incredibly deep tree using recursion can crash the JVM memory stack.
- Losing the root node reference, which instantly destroys the entire tree in memory.
Interview Tips
- Understand that trees are inherently recursive data structures. Writing a recursive traversal is almost always 3 lines of code.
Real-World Example
Binary Trees are used heavily in database indexing (B-Trees) and rendering HTML/XML documents.
example
java
public class DOMNode {
String tag;
DOMNode leftChild;
DOMNode rightSibling;
// Abstract representation of an HTML parser
public void render() {
System.out.println("<" + tag + ">");
}
}