How to find depth of node

Data-structures-theoryHow-ToBeginner · 3 min read

How to Find Depth of a Node in a Tree Data Structure

To find the depth of a node in a tree, count the number of edges from the root node down to that node. This can be done by traversing the tree recursively or iteratively, increasing the depth count each time you move down a level.

📐

Syntax

To find the depth of a node, you typically use a function that takes the root of the tree and the target node as inputs. The function returns the depth as an integer.

root: The starting node of the tree (depth 0).
target: The node whose depth you want to find.
The function traverses the tree, increasing depth by 1 each level.

python

def find_depth(root, target, depth=0):
    if root is None:
        return -1  # target not found
    if root == target:
        return depth
    left = find_depth(root.left, target, depth + 1)
    if left != -1:
        return left
    return find_depth(root.right, target, depth + 1)

💻

Example

This example shows how to find the depth of a node in a simple binary tree. The root node has depth 0, its children have depth 1, and so on.

python

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def find_depth(root, target, depth=0):
    if root is None:
        return -1
    if root == target:
        return depth
    left = find_depth(root.left, target, depth + 1)
    if left != -1:
        return left
    return find_depth(root.right, target, depth + 1)

# Build tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Find depth of node with value 5
target_node = root.left.right
print(find_depth(root, target_node))

Output

⚠️

Common Pitfalls

Not handling the case when the target node is not in the tree, which should return a special value like -1.
Confusing depth with height: depth counts edges from root to node, height counts edges from node to leaf.
For trees with parent pointers, depth can be found by moving up to the root and counting steps.

python

def wrong_find_depth(root, target):
    # This version does not handle missing target and may cause errors
    if root == target:
        return 0
    return 1 + wrong_find_depth(root.left, target)  # fails if target not in left subtree

# Correct approach uses checks and returns -1 if not found

📊

Quick Reference

Remember these key points when finding node depth:

Depth of root node is 0.
Depth increases by 1 for each level down.
Return -1 if node not found.
Use recursion or iteration to traverse the tree.

✅

Key Takeaways

Depth is the number of edges from the root to the node.

Use recursion or iteration to traverse and count depth.

Return -1 if the node is not found in the tree.

Depth of the root node is always zero.

Avoid confusing depth with height of a node.