A binary tree is a hierarchical data structure in which every node has at most two children, commonly called:
- Left child
- Right child
It is a special form of a tree data structure (a non-linear structure used to represent hierarchical relationships).
Learn JavaScript from the comfort of your home
(Root)
/ \
Left RightCore Terminology
✔ Node
The basic storage unit. It contains:
- A value/data
- A reference to left child
- A reference to right child
✔ Root
The topmost node in the tree.
✔ Leaf
A node with no children.
✔ Parent
A node with at least one child.
✔ Child
A node connected below another.
✔ Subtree
A tree within the main tree.
✔ Height of a node
Length of the longest downward path to a leaf.
✔ Depth of a node
Distance from the root to that node.
Characteristics of Binary Trees
- Each node has ≤ 2 children
- The tree is recursive by nature
(each child can itself be treated as a tree) - They can be:
- Complete
- Full
- Perfect
- Balanced
- Degenerate (like a linked list)
Understanding these variations is important.
Apply to learn software engineering at Codeflare’s Academy
Types of Binary Trees
1. Full Binary Tree
Every node has 0 or 2 children.
A
/ \
B C2. Complete Binary Tree
All levels are filled except possibly the last, and nodes are as far left as possible.
3. Perfect Binary Tree
All interior nodes have 2 children and all leaves are at the same level.
4. Balanced Binary Tree
For every node, the height of left and right subtrees differ by at most 1.
(Used for fast searching — e.g., AVL, Red-Black trees)
5. Degenerate Tree
Every parent has only one child, making it behave like a linked list.
Binary Tree vs Binary Search Tree (BST)
A Binary Tree is a general structure.
A Binary Search Tree (BST) is a special binary tree with the rule:
Left subtree values < Node value < Right subtree valuesThis property enables fast search, insertion, deletion (O(log n) average).
Tree Traversal Methods
To access all nodes, you traverse the tree. There are two main categories:
Depth-First Search (DFS) Traversals
1. In-order Traversal (Left → Root → Right)
- Main use: retrieves sorted data from BST.
2. Pre-order Traversal (Root → Left → Right)
- Main use: create a copy of the tree, serialize it.
3. Post-order Traversal (Left → Right → Root)
- Main use: delete the tree, evaluate expressions.
Example Tree:
1
/ \
2 3Traversals:
- In-order → 2, 1, 3
- Pre-order → 1, 2, 3
- Post-order → 2, 3, 1
Breadth-First Search (BFS)
Level-order Traversal
Visit nodes level by level.
Level order → 1, 2, 3, 4, 5...Uses a queue internally.
Operations on Binary Trees
✔ Insertion
Depends on tree type
(e.g., BST inserts smaller values left, larger right).
✔ Deletion
More complex — especially if the node has 2 children.
✔ Searching
DFS or BFS.
✔ Height / Depth Calculations
Used in balancing algorithms.
Binary Tree Implementation (Simplified)
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor(rootValue) {
this.root = new Node(rootValue);
}
// Pre-order traversal (Root → Left → Right)
preorder(node) {
if (node !== null) {
console.log(node.value);
this.preorder(node.left);
this.preorder(node.right);
}
}
}
Example Usage
const tree = new BinaryTree(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.preorder(tree.root);
// Output: 1, 2, 3Applications of Binary Trees
✔ Binary Search Trees (BSTs)
Fast searching, inserting, deleting.
✔ Heaps
Used for priority queues, implemented as complete binary trees.
✔ Syntax Trees / Expression Trees
Used in compilers and interpreters.
✔ Routing Tables, File Systems, AI (decision trees)
✔ Huffman Coding Trees
For file compression algorithms.
Why Binary Trees Matter
They provide:
- Efficient data storage
- Fast lookups
- Hierarchical representation
- Foundation for advanced structures
(BST, AVL, Red-Black Trees, Heaps, Tries)
Binary trees are one of the most fundamental data structures in computer science — understanding them makes advanced algorithms much easier.
About the Author
Latest tech news and coding tips.
