Tree Data Structure: Types, Traversals and a Worked BST Example

Tree terminology, shapes, traversals and BST operations are often revised as separate lists, so one small diagram change causes avoidable errors because the definitions no longer connect. A fixed nine-node BST keeps those relationships checkable because every definition, traversal and operation refers to the same shape. Tree concepts, traversals and BST operations are relevant to GATE CS and other CS exams; current exam-pattern and weightage information belongs to the official notification. Use GATE CS Exam Preparation as the wider subject route.

Binary trees and binary search trees establishes the ordering rule, four traversal definitions and balance intuition. The next layer is classification and representation: classify one nine-node BST as full, complete, perfect or balanced; map it to linked nodes and array indices; then verify insertion, search and deletion traces.

Tree data structure basics: nodes, edges, depth and height

A rooted tree is connected and acyclic. Every non-root node has one parent, and a tree with n nodes has n - 1 edges. Unlike a list, one node can lead to several subtrees. A cycle or second parent breaks the model.

Insert 40, 20, 60, 10, 30, 50, 70, 25, 35 into an empty BST in that order. The root is 40, with children 20 and 60. Node 20 has 10 and 30; node 60 has 50 and 70; node 30 has 25 and 35.

With root depth 0 and height in edges, 20 parents the siblings 10 and 30 and is an ancestor of 35. Leaves are 10, 25, 35, 50, 70; internal nodes are 40, 20, 30, 60. Node 30 has degree 2 and height 1; 25 has depth 3. The tree has 9 nodes, 8 edges, four levels and height 3. Thus "four levels" and "height three" both describe it.

Tree types: binary, full, complete, perfect, balanced and BST

These labels test different properties. Full, complete and perfect are not synonyms, and not every binary tree is a BST.

It is not complete because array positions 8 and 9 are empty while 10 and 11 hold 25 and 35. It is not perfect because 10, 50, 70 are leaves at depth 2, while 25, 35 are at depth 3. The seven-key prefix 40, 20, 60, 10, 30, 50, 70 is full, complete and perfect.

Tree representation: linked nodes versus array indices

A linked record is Node { key, left, right }. Node 30 stores left -> 25 and right -> 35; node 25 stores two null references. This naturally handles an irregular shape.

In a one-based array, left(i)=2i, right(i)=2i+1, and parent(i)=floor(i/2) for i>1. Thus A[5]=30 has children at 10 and 11. Arrays suit complete trees such as heaps. The two null holes show why links are cleaner for an arbitrary BST.

Tree traversals: DFS and BFS on the same nine values

Depth-first search follows one branch before returning. Breadth-first search visits a whole level through a queue.

Inorder sorts BST keys. Postorder handles children before a parent, preorder handles the root first, and level order is breadth-first. For related BFS and DFS question practice, compare graph cases. A tree needs no visited set because each node has one parent and there are no cycles.

Binary search tree operations: insertion, search and deletion

Insertion follows left for a smaller key and right for a larger key.

This uses distinct keys. Duplicate handling is an implementation choice, not an automatic BST rule.

To search for 25, visit 40 -> 20 -> 30 -> 25. Four key comparisons give success. To delete 20, which has two children, take its inorder successor, the minimum key in its right subtree. That key is 25.

1. Copy 25 into the old 20 position.

2. Delete the original 25, which is a leaf.

3. Keep every other parent-child relation unchanged.

The result has root 40. Its left child is 25, with children 10 and 30; 30 has only right child 35. The 60 subtree with 50 and 70 is unchanged. Otherwise, remove a leaf directly or splice a sole child into the deleted node's position.

Tree operation complexity and the traps that change the answer

Let h be height and w be maximum width.

Insert 10, 20, 30, 40, 50 into a plain BST and it forms a right chain of height 4; finding 50 visits five nodes. A balanced arrangement rooted at 30 puts 20, 40 below it and 10, 50 next. Its height is 2, and 50 takes three visits: 30 -> 40 -> 50. A plain BST does not balance itself.

• Calling four levels "height four" causes an off-by-one answer. Check whether height counts edges or nodes.

• Calling every full tree complete misclassifies irregular last levels. Check left-to-right filling.

• Treating every inorder output as sorted gives a false result for a non-BST. Check the search-order property first.

• Quoting O(log n) for a skewed BST understates the cost. Sketch the shape or determine h before choosing complexity.

Tree data structure questions in GATE CS

Concept questions may ask you to identify a traversal, reconstruct a tree from sufficient information, use n-1 edges, distinguish tree types, calculate height or leaf counts, simulate BST operations, or compare balanced and skewed costs. These are concept forms, not current weightage claims.

Use a three-step scratch method:

1. Write the convention, such as height in edges and distinct keys.

2. Annotate depths, child positions or visit order on the tree.

3. Simulate one comparison or visit at a time instead of jumping to an option.

Quick checks catch slips: 9 nodes -> 8 edges; BST inorder increases; every child relation satisfies the rule locally. Use Data Structures MCQs for mixed practice after you can reproduce those checks without the diagram.

Tree data structure: the short version and next step

Retain this sequence: identify the tree type, fix the height convention, write the traversal rule, then simulate BST comparisons node by node. For the running tree, the checks are 9 nodes, 8 edges, height 3, and inorder 10, 20, 25, 30, 35, 40, 50, 60, 70.

If your priority is implementing trees and operations in Java, use DSA using Java as the next step.