Operations on a binary tree – Hierarchical Datastructure

Introduction

This is the eighth article in the series of non-linear data structures, to read more about the previous article, please check the topic Binary Tree – Print all paths in a tree. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

This article is mostly about operations on a binary tree, writing code to delete a binary tree, mirror a binary tree, finding the height of a node and finding the depth of a node. We will use the same tree which we have used till now for all these operations. The tree is shown below:
tree2

Delete a binary tree

This might seem a topic not worth discussing, as it seems so easy. But deleting doesn’t just mean assigning the root to null. While deleting the tree we must take care that there are no un-referenced objects in the memory.

So we need to visit each of the node and then delete or reference each of the nodes to null, one by one. The problem is how shall we approach. As far as the deletion is concerned, we would love to delete the children before deleting the root because if we delete the root first , the reference to the children will be lost.

From the very first article in the hierarchical data structure series, we learnt about the properties of the traversal. There is one traversal technique which prints the root after printing the children. This is what is exactly needed.

Solution

Traverse, the tree in post order, you can use the code from the article Hierarchical Datastructure – Tree Traversals and then instead of printing the node you can simple delete the node.

Here is the pseudo code for the same:
deleteTree

Source Code

What is the time complexity of the algorithm? To delete each node we need to visit each node at least once. Hence the running time would be O(n) where n is the total number of nodes in the tree.

Mirror a binary tree

Mirroring a binary tree is the act of creating a mirror image of the binary tree. For e.g : all the left children must become the right children and all the right children become left children after mirroring.

The mirror of the binary tree shown above looks like the below:
mirrortre
Here is the pseudo code for the same.
mirrorTree
If you notice the pseudo code is similar to the pseudo code for deletign a tree, the only difference is to swap the right and left child of the given node at the present node. This is the definition of mirroring.

Source Code

What is the time complexity of the algorithm? To delete each node we need to visit each node at least once. Hence the running time would be O(n) where n is the total number of nodes in the tree.

Depth & Height of a binary tree

As per the first article in this series Hierarchical Datastructure – detailed discussion we discussed the idea behind calculating the depth and height of a node.

Here is the pseudo code for the depth of a node in a tree.
depthtree
The depth of a node is counted from the root, so the depth of the root is 0 and for every other node the depth is 1 more than it’s parent depth.

Source Code

The running time of the depth algorithm is O(log n) where n is the number of nodes. Reason is that we only visit nodes which lie in the hierarchy from root till the given node whose depth is to be found. And the maximum depth of a binary tree is log n ( base 2). So the maximum running time would be O(log n)

Here is the pseudo code for the height of a node in a tree.
heighttree
The height of a node is counted from the leaf which is farthest from the node, so the height of any leaf is 0 and for every other node the height is 1 more than the max height of either of its children.

Source Code

The asymptotic behaviour of the running time of the height algorithm is O(nlog n) where n is the number of nodes. The reason being the nature of the recurrence which turns out to be T(N) = T(N/2) + T(N/2) + cn
Check this video to solve the recurrence of similar nature

The running time can also prove to be O(N) in cases where the tree is absolutely skewed. Imagine it expands in one leg so we have to visit N nodes to get the height.

Conclusion

In this article we learnt to perform simple operations on a binary tree. These are mostly asked in interviews if not as a complete question then as a part of a complex question. SO it is always good to know these simple operations and its complexity.

Hope this helps, happy reading. Stay connected and stay Subscribed