Trees model hierarchy: each node may have zero or more children, connected by edges. A tree has a single root (no incoming edges), and the route linking two nodes is a path. Key terms: parent, child, siblings, subtree (a node with all descendants), leaf (no children), depth (edges from root to node), and height (max depth of any node).
General (n-ary) trees allow any number of children; binary trees allow at most left and right. Traversals are the workhorses (all O(n)): preorder (node then children), postorder (children then node), and level-order (BFS). Binary trees add inorder (left, node, right). Local rotations are defined only for binary trees and simply rewire a parent/child pair while preserving the left-to-right order of subtrees.
O(1); traversals and metrics like height are O(n). Rotation is O(1).| Operation | General Tree | Binary Tree | Notes |
|---|---|---|---|
add_child(parent, new) |
O(1) | O(1) | Given a pointer/handle to parent; allocation cost ignored. |
delete_subtree(u) |
O(size(u)) | O(size(u)) | Must unlink and free all descendants of u. |
preorder / postorder |
O(n) | O(n) | Each node visited exactly once. |
level_order (BFS) |
O(n) | O(n) | Queue stores up to a full level. |
inorder |
– | O(n) | Defined only for binary trees. |
height |
O(n) | O(n) | Worst-case must inspect all nodes. |
rotate_left/right |
– | O(1) | Local rewiring of pointers; preserves inorder order. |
class Node:
def __init__(self, label):
self.label = label
self.children = [] # for binary: children[0]=left, children[1]=right
self.parent = None
def preorder(u, visit):
if not u: return
visit(u); [preorder(v, visit) for v in u.children]
def postorder(u, visit):
if not u: return
for v in u.children: postorder(v, visit)
visit(u)
from collections import deque
def level_order(root, visit):
if not root: return
q = deque([root])
while q:
u = q.popleft(); visit(u); q.extend(u.children)
# Binary-only helpers
def rotate_left(x):
y = x.children[1] if len(x.children) > 1 else None
if not y: return x
yL = y.children[0] if y.children else None
if len(x.children) < 2: x.children += [None]*(2-len(x.children))
x.children[1] = yL
if yL: yL.parent = x
parent = x.parent
y.parent = parent
x.parent = y
if parent:
idx = 0 if parent.children[0] is x else 1
parent.children[idx] = y
y.children = [x, y.children[1] if len(y.children)>1 else None]
return y if parent is None else parent
def rotate_right(x):
y = x.children[0] if x.children else None
if not y: return x
yR = y.children[1] if len(y.children)>1 else None
if len(x.children) < 2: x.children += [None]*(2-len(x.children))
x.children[0] = yR
if yR: yR.parent = x
parent = x.parent
y.parent = parent
x.parent = y
if parent:
idx = 0 if parent.children[0] is x else 1
parent.children[idx] = y
y.children = [y.children[0] if len(y.children)>0 else None, x]
return y if parent is None else parent
class Node {
String label;
java.util.List<Node> children = new java.util.ArrayList<>();
Node parent;
}
static void preorder(Node u, java.util.function.Consumer<Node> visit){
if(u==null) return; visit.accept(u);
for(Node v: u.children) preorder(v, visit);
}
static void postorder(Node u, java.util.function.Consumer<Node> visit){
if(u==null) return;
for(Node v: u.children) postorder(v, visit);
visit.accept(u);
}
static void levelOrder(Node root, java.util.function.Consumer<Node> visit){
if(root==null) return;
java.util.ArrayDeque<Node> q = new java.util.ArrayDeque<>();
q.add(root);
while(!q.isEmpty()){
Node u=q.remove(); visit.accept(u);
for(Node v: u.children) q.add(v);
}
}
// Binary rotations (assume children.size()<=2)
static void rotateLeft(Node x){
Node y = x.children.size()>1 ? x.children.get(1) : null;
if(y==null) return;
Node yL = y.children.size()>0 ? y.children.get(0) : null;
if(x.children.size()<2) while(x.children.size()<2) x.children.add(null);
x.children.set(1, yL); if(yL!=null) yL.parent = x;
Node p = x.parent; y.parent = p; x.parent = y;
if(p!=null){
int idx = (p.children.get(0)==x) ? 0 : 1;
p.children.set(idx, y);
}
if(y.children.size()<2) while(y.children.size()<2) y.children.add(null);
y.children.set(0, x);
}
static void rotateRight(Node x){
Node y = x.children.size()>0 ? x.children.get(0) : null;
if(y==null) return;
Node yR = y.children.size()>1 ? y.children.get(1) : null;
if(x.children.size()<2) while(x.children.size()<2) x.children.add(null);
x.children.set(0, yR); if(yR!=null) yR.parent = x;
Node p = x.parent; y.parent = p; x.parent = y;
if(p!=null){
int idx = (p.children.get(0)==x) ? 0 : 1;
p.children.set(idx, y);
}
if(y.children.size()<2) while(y.children.size()<2) y.children.add(null);
y.children.set(1, x);
}
struct Node{
std::string label;
std::vector<Node*> children; // for binary: [left,right]
Node* parent = nullptr;
};
void preorder(Node* u, auto visit){
if(!u) return; visit(u);
for(auto v: u->children) preorder(v, visit);
}
void postorder(Node* u, auto visit){
if(!u) return;
for(auto v: u->children) postorder(v, visit);
visit(u);
}
void levelOrder(Node* root, auto visit){
if(!root) return;
std::queue<Node*> q; q.push(root);
while(!q.empty()){
Node* u=q.front(); q.pop(); visit(u);
for(auto v: u->children) q.push(v);
}
}
// Binary rotations (assume children.size()<=2)
void rotateLeft(Node* x){
if(!x || x->children.size()<2) return;
Node* y = x->children[1];
if(!y) return;
Node* yL = (y->children.size()>0)? y->children[0]: nullptr;
x->children[1] = yL; if(yL) yL->parent = x;
Node* p = x->parent; y->parent = p; x->parent = y;
if(p){
int idx = (p->children[0]==x)?0:1;
p->children[idx] = y;
}
if(y->children.size()<2) y->children.resize(2,nullptr);
y->children[0] = x;
}
void rotateRight(Node* x){
if(!x || x->children.empty()) return;
Node* y = x->children[0];
if(!y) return;
Node* yR = (y->children.size()>1)? y->children[1]: nullptr;
if(x->children.size()<2) x->children.resize(2,nullptr);
x->children[0] = yR; if(yR) yR->parent = x;
Node* p = x->parent; y->parent = p; x->parent = y;
if(p){
int idx = (p->children[0]==x)?0:1;
p->children[idx] = y;
}
if(y->children.size()<2) y->children.resize(2,nullptr);
y->children[1] = x;
}
inorder apply only to binary trees?