What is the difference between depth and height in a tree?

Difference Between Depth and Height in a Tree

In the context of tree data structures, "depth" and "height" are two fundamental concepts that describe different properties of the nodes and the tree itself. Understanding the difference between these terms is crucial for working with trees effectively.

Depth

• Definition: The depth of a node in a tree is the number of edges from the root node to the node.
• Root Node: The depth of the root node is always 0, as there are no edges from the root to itself.
• Calculation: The depth of any node n can be calculated as the depth of its parent node plus one.

Example: Consider the following tree:

         A
       /   \
      B     C
     / \   / \
    D   E F   G

• Depth of A: 0 (root node)
• Depth of B: 1 (one edge from A to B)
• Depth of D: 2 (two edges from A to B to D)

Height

• Definition: The height of a node in a tree is the number of edges on the longest path from the node to a leaf.
• Leaf Nodes: The height of all leaf nodes is 0, as there are no edges to any child nodes.
• Tree Height: The height of the tree is the height of the root node, which is the number of edges on the longest path from the root to a leaf.

Example: Consider the same tree:

         A
       /   \
      B     C
     / \   / \
    D   E F   G

• Height of D: 0 (leaf node)
• Height of B: 1 (one edge to D or E, both are leaf nodes)
• Height of A: 2 (two edges on the longest path to D or E or F or G)

Key Differences

• Depth:

  • Relates to the distance from the root to a specific node.
  • Indicates how deep a node is situated within the tree.
  • Depth of root node is 0.

• Height:

  • Relates to the distance from a specific node to the furthest leaf node.
  • Indicates how tall a node's subtree is.
  • Height of leaf nodes is 0.
  • Height of the tree is the height of the root node.

Visual Representation

Here is a visual representation to further clarify the concepts:

         A (Depth: 0, Height: 2)
       /   \
      B     C
   (Depth: 1) (Depth: 1)
   (Height: 1) (Height: 1)
     / \   / \
    D   E F   G
(Depth: 2) (Depth: 2) (Depth: 2) (Depth: 2)
(Height: 0) (Height: 0) (Height: 0) (Height: 0)

Summary

• Depth of a Node: The number of edges from the root node to the node.
• Height of a Node: The number of edges on the longest path from the node to a leaf.
• Depth of Tree: Not defined as a whole tree property; typically refers to the depth of individual nodes.
• Height of Tree: The height of the root node, which is the number of edges on the longest path from the root to a leaf.

Understanding these concepts is essential for various tree operations and algorithms, such as traversals, balancing, and searching. For more in-depth knowledge and practical examples on tree data structures and other programming concepts, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.