Binary trees: structure and traversals

A branching structure, not a sorting rule

A linked-list node gave us one next link. A binary-tree node has two named child positions, left and right, either of which may be absent. Those names matter: a node with only a left child and a node with only a right child have different ordered structure. “Binary” limits the number of children to two; it says nothing about the numerical order of stored values.

You will identify roots, leaves, depth and height; distinguish common shape conditions; and trace preorder, inorder and postorder. This lesson bridges the bounded linked-list representation and the earlier recursion lessons. Read “Singly linked lists: nodes, links and traversal” first, and recall a recursive call's own arguments, a base case and returning to pending work. You also need arrays, valid indices, loops/conditions and C functions. The small new record and validator details are explained below.

This is an introductory tree lesson. It does not teach BST search, heap operations, balancing, graph traversal, reconstruction from traversal pairs or complete GATE CS coverage. BSTs and heaps come next and add different rules. The example deliberately violates BST ordering so that tree shape is not mistaken for sortedness.

The structural vocabulary

A nonempty rooted tree has one root, with no parent. Every other node has exactly one parent. Child links contain no cycle, and every member is reachable from the root. A parent and child are joined by one edge. For n > 0 nodes, there are n - 1 edges: each node except the root contributes its unique incoming parent edge.

• A leaf has no children. A node with one or two children is an internal node.
• A subtree rooted at a node consists of that node and all nodes reached below it. A missing child position represents an empty subtree.
• A node's depth is the number of edges from the root to it. The root has depth 0.
• A node's height is the greatest number of edges from it down to a leaf. A leaf has height 0. The tree's height is the root's height.
• We define the empty tree's height as -1. This is a useful convention, not a claim that an actual path has negative length. Some sources count nodes instead of edges; identify the convention before answering.

“Level d” here means depth d. A nonempty height-h tree therefore occupies h + 1 levels, from 0 through h. Depth looks upward from a node to the root; height looks downward to a farthest leaf. They are not interchangeable. A parent need not be stored immediately before a child in memory, and equal data values can belong to different nodes.

Full, complete and perfect are different shape conditions

For nonempty binary trees, use these definitions throughout:

• Full (proper/strict): every node has either zero or two children; no node has exactly one.
• Complete: every level except possibly the last is full, and the last level is filled from left to right with no gap.
• Perfect: every internal node has two children and all leaves have the same depth; equivalently every occupied level is full.

A root with only a left leaf is complete, but not full or perfect. A root with only a right leaf is not complete, because the left position is a gap. A root with two leaf children is all three. A full tree can be unbalanced and fail completeness: for example, a root with a left leaf and a right child that has two leaf children. Its deepest level has nodes on the right after gaps on the left.

These definitions concern shape alone. Do not test them by comparing node values. A BST can have a long one-child chain; a binary heap needs a complete shape. Those later structures add value-order rules of their own.

A bounded index representation

We use a C11 array of seven initialized records. Each record stores value, left and right. A child link is an array index or END = -1. The field selects its meaning: the data value -1 is allowed, while a child link -1 means no child. The root is also an index or END. There is no heap allocation, pointer-linked node ownership, deletion or memory release in this program.

typedef struct { int value; int left; int right; } Node; names a three-field record type. nodes[4].left selects the left field of array record 4. An initializer {8, 1, 5} sets the three fields in that order. enum { CAP = 7, END = -1 }; gives integer constants names.

Our storage contract requires an actual live array of CAP initialized records. The active nodes occupy indices 0 through used - 1, with 0 <= used <= CAP. All active nodes must belong to the single rooted tree. Unused records are not members. Every active node is reached exactly once, through a child link, except the root, which is reached from the root variable. With used = 0, root must be END.

The validator checks these field-level rules, including cycles, shared children and unreachable active nodes. It cannot discover whether a caller really supplied seven live initialized records; that remains the caller's responsibility. The traversal and height helpers require a tree already accepted by the validator, kept unchanged while they run. They are not stand-alone validators for arbitrary indices. All calls are sequential.

const Node nodes[] uses C's array-parameter convention: it refers to the original array without copying all records, and disallows writes through that parameter. In contrast, int seen[] permits writes into the caller's visited-marker array. The address is still passed by value; changing seen[at] changes that shared array element. There is no new copy of the markers per recursive call. The validator creates one fresh zero-initialized seen array for each whole validation.

Worked trace 1: read links, then name the structure

With root = 4 and used = 7, describe the tree by values (which happen to be distinct here): root 8 has left child 12 and right child 3. Node 12 has children 2 and 5. Node 5 has only left child 9. Node 3 has only right child 7. Links refer to indices, so index 5 holds value 3; do not confuse the node whose value is 5 with array slot 5.

Depth 0 contains value 8; depth 1 contains 12, 3; depth 2 contains 2, 5, 7; depth 3 contains 9. Leaves are 2, 9 and 7. There are seven nodes and six edges. The deepest path is 8 -> 12 -> 5 -> 9: three edges and four nodes, so height is 3. It is not full because two nodes have one child; it is not complete because the left-child position under 3 is a gap before its right child 7; it is not perfect. It is still a valid binary tree.

The three depth-first orders

At every nonempty subtree, keep the left subtree before the right subtree. Place the current node's visit in one of three positions:

• Preorder: node, left, right. Visit this node before either child subtree.
• Inorder: left, node, right. Visit this node between its two child subtrees.
• Postorder: left, right, node. Visit this node after both child subtrees.

Visiting means printing the node's data in this program. Reaching END visits nothing and returns immediately. These are recursive rules for each entire subtree, not instructions to print just the two immediate children and move on. The function enters a call at the node in all three orders; what changes is when printing happens relative to its child calls.

Complete C11 program

Predict the three printed sequences. Only a valid tree reaches the traversal calls.

#include <stdio.h>

enum { CAP = 7, END = -1 };

typedef struct {
    int value;
    int left;
    int right;
} Node;

int check_visit(const Node nodes[], int used, int at, int seen[]) {
    if (at == END) {
        return 0;
    }
    if (at < 0 || at >= used || seen[at]) {
        return -1;
    }
    seen[at] = 1;
    int left_count = check_visit(nodes, used, nodes[at].left, seen);
    if (left_count < 0) {
        return -1;
    }
    int right_count = check_visit(nodes, used, nodes[at].right, seen);
    if (right_count < 0) {
        return -1;
    }
    return 1 + left_count + right_count;
}

int valid_tree(const Node nodes[], int used, int root) {
    if (used < 0 || used > CAP) {
        return 0;
    }
    int seen[CAP] = {0};
    int count = check_visit(nodes, used, root, seen);
    return count >= 0 && count == used;
}

void preorder(const Node nodes[], int at) {
    if (at == END) {
        return;
    }
    printf("%d ", nodes[at].value);
    preorder(nodes, nodes[at].left);
    preorder(nodes, nodes[at].right);
}

void inorder(const Node nodes[], int at) {
    if (at == END) {
        return;
    }
    inorder(nodes, nodes[at].left);
    printf("%d ", nodes[at].value);
    inorder(nodes, nodes[at].right);
}

void postorder(const Node nodes[], int at) {
    if (at == END) {
        return;
    }
    postorder(nodes, nodes[at].left);
    postorder(nodes, nodes[at].right);
    printf("%d ", nodes[at].value);
}

int height(const Node nodes[], int at) {
    if (at == END) {
        return -1;
    }
    int left_height = height(nodes, nodes[at].left);
    int right_height = height(nodes, nodes[at].right);
    if (left_height > right_height) {
        return 1 + left_height;
    }
    return 1 + right_height;
}

int main(void) {
    Node nodes[CAP] = {
        {2, END, END},
        {12, 0, 3},
        {9, END, END},
        {5, 2, END},
        {8, 1, 5},
        {3, END, 6},
        {7, END, END}
    };
    int used = 7;
    int root = 4;
    if (!valid_tree(nodes, used, root)) {
        return 1;
    }
    printf("pre: ");
    preorder(nodes, root);
    printf("\nin: ");
    inorder(nodes, root);
    printf("\npost: ");
    postorder(nodes, root);
    printf("\nheight: %d\n", height(nodes, root));
    return 0;
}

Exact output (there is a space after each printed node value):

pre: 8 12 2 5 9 3 7 
in: 2 12 9 5 8 3 7 
post: 2 9 5 12 7 3 8 
height: 3

Worked trace 2: resolve whole subtrees

First resolve the subtree rooted at value 12. Its left subtree is the leaf 2; its right subtree is rooted at 5 with left leaf 9.

For inorder at value 8, the entire left subtree prints first: 2, 12, 9, 5. Only then does 8 print, followed by the right subtree's 3, 7. Inorder is not necessarily sorted: this is a general binary tree, not a BST.

For postorder at value 12, its call waits for the leaf 2 and then the entire subtree at 5 before printing 12. The earlier recursion idea of pending work explains this order. Each nonempty node prints exactly once in each traversal. Empty-child calls do not print; “visit count” does not mean total function-call count. Traversal does not rewrite links or physically move records.

Worked trace 3: compute heights after returns

The height helper returns -1 for an empty subtree, then adds 1 to the greater child height for a node. The addition occurs after both child calls have returned.

Node 3 has depth 1 and height 1; node 5 has depth 2 and height 1. Leaves can have different depths while all still have height 0. The empty base value makes the one-node result 1 + max(-1,-1) = 0. In a valid tree with at most seven nodes, height ranges from -1 (empty) to 6 (a seven-node chain), and all additions remain small.

Safety and the validator's shared markers

check_visit returns 0 for END, a node count for a valid subtree and -1 on invalid structure. Here -1 is a validation result, separate from stored payloads. It checks an index before reading either nodes[at] or seen[at]. The logical OR operator || short-circuits: if at < 0 or at >= used, the later seen[at] expression is not evaluated. The marker is set before descending. Seeing the same index again rejects a cycle or a child shared by two parents. Each accepted real-node entry marks a previously unseen index, so there can be at most used such entries before termination or rejection.

Left and right counts are assigned by separate calls, with an early return on a failed child. A successful total cannot exceed seven. The outer validator also checks count == used, so disconnected active nodes are not silently ignored. A malformed root, out-of-range child, repeated child, self-link or disconnected active record fails. For the valid empty representation, both used and the returned count are zero.

The traversal base cases test END before reading a record. A valid structure has no cycles or shared nodes, so every node is visited once and the recursive descent terminates. The validator's precondition is essential: calling preorder directly on an unchecked cycle would not be protected by preorder's END test alone. This is a small bounded example, not a guarantee of safe recursion depth for arbitrary tree sizes.

void traversal functions do not return a value; return; ends an empty-child call. int seen[CAP] = {0} initializes all seven markers to zero. && means logical AND; ! tests for zero. <stdio.h> declares printf; %d prints an int and \n starts a line. The data values are only read and printed, never added or compared for ordering.

A precise analogy

Imagine a labeled folder that may have a left subfolder and a right subfolder. To record every folder label, you can record a folder before its subfolders, between the left and right subfolders, or after both. Empty subfolder positions require no label. This models the three recursive visit positions. The analogy assumes each subfolder belongs to one parent and that folders never contain themselves through links; real shortcuts or shared folders would require different rules. “Left” and “right” are positions, not smaller and larger labels.

Key box

• A binary tree has at most two ordered child positions per node; it need not be a BST.
• One root, one parent for each other node, reachability and no cycles define the rooted structure here.
• Depth and height count edges; root depth and leaf height are 0, empty-tree height is defined as -1.
• Full, complete and perfect test different shape conditions, not values.
• Pre/in/post place the current visit before/between/after the child traversals.
• Inorder sorts values only when a suitable BST ordering rule also holds.
• END is a missing link; stop before indexing. Validate before calling the traversal helpers.

Try it first, then check

1. A root A has only right child B, and B has only left child C. Write all traversals and height. Answer: preorder A,B,C; inorder A,C,B; postorder C,B,A; height 2 edges. The shape is neither full, complete nor perfect.
2. A single node has value -1 with both child links END. Is it empty? Answer: no. All three traversals print the data -1 once; height is 0. The empty tree has root = END and used = 0 and prints no node.
3. Keep the main tree but give node at index 5 a left link to index 0, which is already the left child of index 1. Answer: validation rejects the shared child; one node would have two parents. Repeating a data value instead would be allowed because node identity is its index, not its payload.

Six original practice questions

Choose exactly one option. These are original foundation exercises, not official previous-year questions, a full mock or a claim of complete syllabus coverage. Use the explicit definitions above.

1

Root A has left child B and right child C. B has only right child D; C and D are leaves. What is the postorder sequence?

A. A, B, D, C B. B, D, A, C C. D, C, B, A D. D, B, C, A

2

Using this lesson’s edge-count convention, a tree is a chain of seven nodes. What are its height and the depth of its last node?

A. 7 and 7 B. 6 and 6 C. 6 and 0 D. 0 and 6

3

A nonempty binary tree contains a root with only one left child, which is a leaf. Which shape classification is correct?

A. Full and perfect, but not complete B. Full and complete, but not perfect C. Complete, but neither full nor perfect D. None of full, complete or perfect

4

In the main program’s tree, which is the complete inorder DATA sequence?

A. 0, 1, 2, 3, 4, 5, 6 B. 2, 12, 9, 5, 8, 3, 7 C. 2, 3, 5, 7, 8, 9, 12 D. 8, 12, 2, 5, 9, 3, 7

5

Two different active parents point to the same child index. There is no directed cycle. What does this lesson’s validator do?

A. Rejects the shared child because the second encounter finds its seen marker already set B. Accepts it because absence of cycles is the only tree rule C. Copies the child automatically so each parent gets a private copy D. Accepts only if the two parents have different data values

6

For a valid empty representation (used=0, root=END), what do preorder and height do when called as shown after validation?

A. preorder prints -1; height returns 0 B. preorder reads nodes[-1]; height returns -1 C. preorder prints nothing; height returns 0 D. preorder prints nothing; height returns -1

Worked answers

1: D

A is incorrect: node-before-children gives preorder.

B is incorrect: left-node-right gives inorder for this tree.

C is incorrect: the entire subtree at B, including B itself, must finish before the right subtree at C.

D is correct: the left subtree gives D,B; the right gives C; the root A is visited last.

2: B

A is incorrect: seven nodes on the path give six connecting edges.

B is correct: the longest root-to-leaf path has six edges, so both quantities are 6.

C is incorrect: 0 is the last node’s own height because it is a leaf, not its depth from the root.

D is incorrect: the whole tree has height 6; only a leaf has height 0.

3: C

A is incorrect: the root has exactly one child, violating both full and perfect.

B is incorrect: complete is true, but full forbids the root’s one-child case.

C is correct: the last level begins in the leftmost position without a gap; the root’s one child prevents full and perfect.

D is incorrect: this is complete because the only last-level node is leftmost.

4: B

A is incorrect: it is an ascending list of physical indices, not a traversal of data.

B is correct: the left subtree gives 2,12,9,5; then root 8; then right subtree 3,7.

C is incorrect: this is sorted data. A general binary tree does not guarantee sorted inorder.

D is incorrect: printing the root before its subtrees gives this tree’s preorder.

5: A

A is correct: every nonroot node must have one parent. The shared seen array detects the repeated index even without a cycle.

B is incorrect: single-parent membership and reachability are also required.

C is incorrect: passing these array parameters does not duplicate records.

D is incorrect: node identity is its index; parent data comparisons do not repair multiple parents.

6: D

A is incorrect: END is not a node payload here, and empty height is defined as -1, not 0.

B is incorrect: both helpers test END before any nodes[at] read.

C is incorrect: the output behavior is right, but height 0 belongs to a one-node tree under the edge convention.

D is correct: the base cases immediately return, with no print or node read and the defined empty height -1.

Next step and scope

Next, add a BST ordering rule to tree structure, then study the different complete-shape and parent-order rules of a binary min-heap. This original C11 foundation does not relabel an existing examination year or claim complete course coverage. Hindi explanations are a learning aid.