Concept of Tree

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Concept of Tree: the first non-linear structure

Everything before this chapter was a straight line. A tree branches — and that one change is what makes searching fast.

What makes something a tree

A tree is a hierarchical structure: one root at the top, every other node having exactly one parent, and any number of children. Nodes with no children are leaves.

The defining property is not the branching — it is that there is exactly one path between any two nodes. No node has two parents, and no path loops back on itself. A structure that allows either is a graph, not a tree, and almost every tree algorithm depends on that uniqueness: it is why recursion terminates and why no visited-set is needed.

The vocabulary, and what each term measures

🌳 Terms worth being precise about

RootThe only node with no parent. A tree has exactly one.

LeafA node with no children. Also called an external node.

Degree of a nodeHow many children it has. The degree of the TREE is the largest degree of any node in it.

SiblingNodes sharing the same parent.

Ancestor / descendantAny node on the path up to the root; any node reachable going down.

SubtreeAny node together with all of its descendants — itself a valid tree, which is why recursion works so cleanly here.

Binary trees, and why they dominate

A binary tree restricts every node to at most two children, conventionally called left and right. The restriction sounds arbitrary and is the reason the structure is useful: with exactly two directions, a comparison at each node — smaller or larger — decides which way to go.

Special shapes worth naming: Full every node has either 0 or 2 children, never 1 Complete every level filled except possibly the last, which fills from the LEFT Perfect every level completely filled Skewed every node has one child — degenerates into a linked list, and every advantage is lost A complete binary tree is what lets a heap live in a plain array with no pointers: children of index i sit at 2i+1 and 2i+2.

💡 The skewed case is the one examiners use. Insert 1, 2, 3, 4, 5 into a binary search tree in that order and every node becomes the right child of the last — the tree is a linked list wearing a tree's structure, and search degrades from O(log n) to O(n). That failure is the entire motivation for AVL and other self-balancing trees.

Where the speed comes from

In a balanced tree, each step down eliminates roughly half the remaining nodes, so reaching any node takes about log₂n steps. A thousand nodes is about ten steps; a million is about twenty. That collapse is why trees are used for searching and why keeping them balanced matters more than any other property.

Commonly confused

Tree and graph. A tree is a connected graph with no cycles. Every tree is a graph; almost no graph is a tree.

Height and depth. Covered in the next chapter, and consistently mixed up: depth is measured downward from the root, height upward from the leaves.

Full and complete. Full is about the number of children (0 or 2); complete is about how the levels are filled.

Rapid revision

One root, one parent each, exactly one path between any two nodes.

Degree = number of children; the tree's degree is the maximum.

Binary tree: at most two children, so one comparison chooses the direction.

A skewed tree is a linked list — O(n), and the reason balancing exists.

Syllabus points

Tree terminology and definitions

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.