Binary Tree Introduction
Tree Basics
A binary tree is a hierarchical structure where each node has at most two children, conventionally called the left child and the right child. It's the foundation for many more specialized structures like binary search trees and heaps that add extra rules on top of this basic shape.
Example: Tree Basics
#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node root = {1, nullptr, nullptr};
cout << "Root value: " << root.val << ", left/right are null" << endl;
return 0;
}public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node root = new Node(1);
System.out.println("Root value: " + root.val + ", left/right are null");
}
}class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
root = Node(1)
print("Root value:", root.val, ", left/right are None")#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
struct Node root = {1, NULL, NULL};
printf("Root value: %d, left/right are null\n", root.val);
return 0;
}Login to try C/C++/Java code in the editor
Tree Node
Each node in a binary tree typically stores a value along with two references (or pointers) to its children — either of those references can be null if that child doesn't exist, which is how leaf nodes and single-child nodes are represented.
Example: Tree Node
#include <iostream>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
int main() {
Node* n = new Node(5);
cout << "Node value=" << n->val << " left=" << n->left << " right=" << n->right << endl;
return 0;
}public class Main {
static class Node {
int val; Node left, right;
Node(int v) { val = v; left = null; right = null; }
}
public static void main(String[] args) {
Node n = new Node(5);
System.out.println("Node value=" + n.val + " left=" + n.left + " right=" + n.right);
}
}class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
n = Node(5)
print("Node value=", n.val, "left=", n.left, "right=", n.right)#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
struct Node n = {5, NULL, NULL};
printf("Node value=%d left=%p right=%p\n", n.val, (void*)n.left, (void*)n.right);
return 0;
}Login to try C/C++/Java code in the editor
Tree Structure
The tree as a whole starts from a single root node, with every other node reachable by following child links downward from it — this connectedness (plus the absence of cycles) is what distinguishes a tree from a more general graph structure.
Example: Tree Structure
#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node c1 = {2, nullptr, nullptr};
Node c2 = {3, nullptr, nullptr};
Node root = {1, &c1, &c2};
cout << "Reached child via root: " << root.left->val << ", " << root.right->val << endl;
return 0;
}public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
System.out.println("Reached child via root: " + root.left.val + ", " + root.right.val);
}
}class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Reached child via root:", root.left.val, ",", root.right.val)#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
struct Node c1 = {2, NULL, NULL}, c2 = {3, NULL, NULL};
struct Node root = {1, &c1, &c2};
printf("Reached child via root: %d, %d\n", root.left->val, root.right->val);
return 0;
}Login to try C/C++/Java code in the editor
Leaf and Internal Nodes
A leaf node has no children at all, sitting at the bottom of some branch of the tree, while an internal node has at least one child and sits somewhere between the root and the leaves.
Example: Leaf and Internal Nodes
#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node leaf = {3, nullptr, nullptr};
Node internal = {1, &leaf, nullptr};
cout << (leaf.left == nullptr && leaf.right == nullptr ? "leaf is a leaf node" : "not a leaf") << endl;
cout << (internal.left != nullptr ? "internal is an internal node" : "not internal") << endl;
return 0;
}public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node leaf = new Node(3);
Node internal = new Node(1);
internal.left = leaf;
System.out.println(leaf.left == null && leaf.right == null ? "leaf is a leaf node" : "not a leaf");
System.out.println(internal.left != null ? "internal is an internal node" : "not internal");
}
}class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
leaf = Node(3)
internal = Node(1)
internal.left = leaf
print("leaf is a leaf node" if leaf.left is None and leaf.right is None else "not a leaf")
print("internal is an internal node" if internal.left is not None else "not internal")#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
struct Node leaf = {3, NULL, NULL};
struct Node internal = {1, &leaf, NULL};
printf("%s\n", (leaf.left == NULL && leaf.right == NULL) ? "leaf is a leaf node" : "not a leaf");
printf("%s\n", internal.left != NULL ? "internal is an internal node" : "not internal");
return 0;
}Login to try C/C++/Java code in the editor
Binary Tree Practice
Binary trees are built recursively in practice: a tree is either empty, or it's a node with a left subtree and a right subtree, each of which is itself a smaller binary tree — this recursive definition is exactly why recursive algorithms fit trees so naturally.
Example: Binary Tree Practice
#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int countNodes(Node* n) {
if (n == nullptr) return 0;
return 1 + countNodes(n->left) + countNodes(n->right);
}
int main() {
Node c1 = {2, nullptr, nullptr}, c2 = {3, nullptr, nullptr};
Node root = {1, &c1, &c2};
cout << "Total nodes: " << countNodes(&root) << endl;
return 0;
}public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
static int countNodes(Node n) {
if (n == null) return 0;
return 1 + countNodes(n.left) + countNodes(n.right);
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
System.out.println("Total nodes: " + countNodes(root));
}
}class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_nodes(n):
if n is None:
return 0
return 1 + count_nodes(n.left) + count_nodes(n.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Total nodes:", count_nodes(root))#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int countNodes(struct Node* n) {
if (n == NULL) return 0;
return 1 + countNodes(n->left) + countNodes(n->right);
}
int main() {
struct Node c1 = {2, NULL, NULL}, c2 = {3, NULL, NULL};
struct Node root = {1, &c1, &c2};
printf("Total nodes: %d\n", countNodes(&root));
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: