Height and Depth of a Binary Tree
Introduction to Height and Depth of a Binary Tree
The height of a tree is a property of the entire tree and measures the longest path from the root to a leaf, while the depth of a node is specific to an individual node and represents its position within the tree in terms of the path from the root. These concepts are essential for understanding and analyzing tree data structures and are fundamental in various algorithms and data manipulation operations.
Let’s jump into the article to know more about Height and Depth of a Tree with its various applications.
Height and Depth of a Tree
Height of a Tree in data structure
The height of a tree is a measure of its vertical or top-down extent. It is defined as the length of the longest path from the root node to any leaf node in the tree. In other words, it represents the number of edges or levels in the longest path from the root to a leaf.
- The height of a tree is a crucial metric because it indicates how balanced or skewed the tree is.
- A balanced tree, like a binary search tree, has a relatively small height, making operations like searching, insertion, and deletion more efficient, as they have a time complexity of O(log n).
- In contrast, a highly unbalanced tree can have a height close to n (the number of nodes), resulting in less efficient operations with a time complexity of O(n).
Depth of a Tree in data structure
The depth of a node in a tree refers to the length of the path from the root node to that specific node. It measures how many edges or levels are traversed to reach that node from the root.
- The depth of a node is used to determine its position within the tree and its relationship with other nodes.
- For example, the depth of the root node is always 0, and the depth of nodes in the subsequent levels increases by one.
Height and Depth of a Tree Example
Difference between Height and Depth of a Tree
| Aspect | Height of a Tree | Depth of a Tree |
|---|---|---|
| Definition | The height of a tree is the length of the longest path from the root node to any leaf node in the tree. It measures the overall vertical extent of the tree. | The depth of a node is the length of the path from the root node to that specific node, indicating its position within the tree. |
| Focus | Concerns the entire tree structure. | Focuses on individual nodes within the tree. |
| Minimum Value | The minimum height of any tree is 0, which occurs in a tree with just one node (the root node). | The depth of the root node is always 0, indicating that it is at the top level of the tree. |
| Maximum Value | The maximum height of a tree is equal to the number of levels in the tree. In a perfectly balanced binary tree with ‘n’ nodes, the height is log₂(n). | The maximum depth of a node is equal to the height of the tree, as a node at the deepest level has the same depth as the tree’s height. |
| Use Cases | Important for assessing the overall balance and performance of the tree. | Useful for identifying the relative positions of nodes in the tree and for node-specific operations. |
Program to find Height of a Tree in Python
Certainly! Here’s a Python code to calculate the height of a binary tree using a recursive approach:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def tree_height(root):
if root is None:
return 0
left_height = tree_height(root.left)
right_height = tree_height(root.right)
# The height of the tree is the maximum of the left and right subtrees' heights, plus 1 for the current node.
return max(left_height, right_height) + 1
# Create a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
# Calculate the height of the tree
height = tree_height(root)
print("Height of the tree:", height)
Output :
Height of the tree: 3
Explanation :
The code calculates the height of a binary tree, which is the length of the longest path from the root node to a leaf node. It uses a recursive approach to traverse the tree, finding the maximum height between the left and right subtrees and adding 1 for the current node. The example binary tree provided has a height of 3, as the longest path from the root to a leaf involves three edges.
Program to find Depth of a Tree in Python
Implementation of node depth in a binary tree for printing the output:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def node_depth(root, key, depth=0):
if root is None:
return -1 # Node not found
if root.value == key:
return depth
left_depth = node_depth(root.left, key, depth + 1)
if left_depth != -1:
return left_depth
right_depth = node_depth(root.right, key, depth + 1)
return right_depth
# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
node_value = 5
depth = node_depth(root, node_value)
if depth != -1:
print("Depth of node " + str(node_value) + ": " + str(depth))
else:
print("Node " + str(node_value) + " not found in the tree.")
Output :
Depth of node 5: 2
Explanation :
This Python code calculates the depth of a specific node within a binary tree. It employs a recursive approach to traverse the tree, incrementing the depth at each step. If the target node is found, its depth is returned; otherwise, -1 is returned to indicate that the node is not in the tree. The code then prints the depth of the specified node or a message if the node is not found.
Complexity analysis for Height and Depth of a Binary Tree
The complexity analysis for calculating the height and depth of a binary tree involves both time and space complexity. Here’s the breakdown:
Time Complexity:
Calculating Height:
- Time complexity for calculating the height of a binary tree is O(n), where n is the number of nodes in the tree. This is because the algorithm visits every node in the tree exactly once to determine the height.
Calculating Node Depth:
- Calculating the depth of a specific node has a time complexity of O(n), similar to calculating the height. In the worst case, the algorithm may have to traverse all nodes to find the target node.
Space Complexity:
- The space complexity for both operations depends on the method used to traverse the tree.
- If a recursive approach is used, the space complexity is O(h), where h is the height of the binary tree. This is because the call stack can grow to the height of the tree during the recursive traversal.
- If an iterative approach using a stack or queue is employed, the space complexity is also O(h) in the worst case. The space used is proportional to the maximum number of nodes at any level.
To Wrap it up:
In the context of tree data structures, “height” refers to the measurement of a tree’s vertical extent. It represents the length of the longest path from the root node to any leaf node in the tree. On the other hand, “depth” signifies the position of a specific node within the tree. It quantifies the length of the path from the root node to the node of interest. This depth information is invaluable for targeted node access and hierarchical relationships within the tree.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment