Depth

Definition

Depth of a node in a tree is the number of edges on the path from the root node to that node.

• The root node has depth 0
• Its children have depth 1
• Their children have depth 2, and so on

If a node is located three edges away from the root, then its depth is 3.

In many academic contexts, depth is closely related to level:

• Depth of a node = number of edges from root
• Level of a node is often depth + 1, depending on the convention used

Main Content

1. First Concept: Depth of a Node

Meaning of depth

• : The depth of a node tells how far that node is from the root. It is measured by counting the edges in the path from the root to that node.

Example in a tree

• :

          A
        /   \
       B     C
      / \     \
     D   E     F

Here:

• Depth of A = 0
• Depth of B = 1
• Depth of C = 1
• Depth of D = 2
• Depth of E = 2
• Depth of F = 2

This shows that nodes closer to the root have smaller depth values.

2. Second Concept: Depth and Root-to-Node Path

Path relationship

• : Depth is directly connected to the path from the root. If the path contains more edges, the node is deeper in the tree.

Counting edges carefully

• : Depth is counted using edges, not nodes. This is very important because students often mistakenly count the number of nodes in the path.

For example, if the path is:

Root -> Child -> Grandchild -> Great-Grandchild

There are 3 edges, so the depth of the great-grandchild is 3.

This concept is useful when analyzing nested structures such as folder systems, XML trees, or expression trees.

3. Third Concept: Depth in Relation to Tree Structure

Balanced vs unbalanced trees

• : In a balanced tree, depths of leaves are usually similar. In an unbalanced tree, some nodes may have much larger depth than others.

Importance in operations

• : Depth affects how efficiently a tree can be searched, inserted into, or traversed. Smaller depth often means faster access.

Example of deeper structure:

    A
     \
      B
       \
        C
         \
          D

Here, node D has depth 3, showing an unbalanced tree. Such a tree may behave more like a linked list and reduce performance.

Working / Process

1. Identify the root node

• Start at the root, because depth is measured from the root downward.
• The root always has depth 0.

2. Count the edges along the path

• Move from the root to the target node.
• Count every edge crossed.
• The total number of edges is the node’s depth.

3. Assign depth values to all nodes

• Apply the same rule to every node in the tree.
• This helps in labeling, comparing, and analyzing the tree structure.
• Example:

          10
        /    \
       5      15
      / \       \
     2   7       20

Depth values:

• 10 → 0
• 5, 15 → 1
• 2, 7, 20 → 2

Advantages / Applications

Helps in tree analysis

• : Depth is used to understand how nodes are positioned in a tree and how complex the tree structure is.

Useful in algorithm design

• : Many tree algorithms, such as traversals, balancing, and search operations, depend on depth values.

Applied in real-world structures

• : Depth is important in file systems, organization charts, DOM trees, parse trees, and decision trees.

Summary

• Depth tells how far a node is from the root.
• It is counted by the number of edges on the path from the root.
• Depth is a basic but very important tree concept.

Important terms to remember: root, node, edge, path, depth.