## 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:

## 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:

### Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
public class DeleteTree { static LinkedBinaryTree myTree = new LinkedBinaryTree(); public static void main(String[] args) throws InvalidPositionException, NonEmptyTreeException, BoundaryViolationException { BTNode root = createTree(); deleteTree(root); root = null; } public static void deleteTree(BTNode node) throws NonEmptyTreeException, InvalidPositionException, BoundaryViolationException { if (node == null) return; try { deleteTree((BTNode) myTree.left(node)); } catch (Exception e) { } try { deleteTree((BTNode) myTree.right(node)); } catch (Exception e) { } myTree.remove(node); } public static BTNode createTree() throws NonEmptyTreeException, InvalidPositionException { BTNode root = (BTNode) myTree.addRoot("ROOT"); BTNode P1 = (BTNode) myTree.insertLeft(root, "P1"); BTNode P3 = (BTNode) myTree.insertRight(root, "P3"); BTNode C1 = (BTNode) myTree.insertLeft(P1, "C1"); BTNode C2 = (BTNode) myTree.insertRight(P1, "C2"); BTNode C4 = (BTNode) myTree.insertLeft(P3, "C4"); BTNode C5 = (BTNode) myTree.insertRight(P3, "C5"); BTNode L1 = (BTNode) myTree.insertLeft(C1, "L1"); BTNode L2 = (BTNode) myTree.insertLeft(C2, "L2"); BTNode L5 = (BTNode) myTree.insertRight(C4, "L5"); return root; } } |

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:

Here is the pseudo code for the same.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class MirrorTree { static LinkedBinaryTree myTree = new LinkedBinaryTree(); public static void main(String[] args) throws InvalidPositionException, NonEmptyTreeException, BoundaryViolationException { BTNode root = createTree(); mirrorTree(root); System.out.println(); } public static void mirrorTree(BTNode node) throws NonEmptyTreeException, InvalidPositionException, BoundaryViolationException { if (node == null) return; mirrorTree((BTNode) node.getLeft()); mirrorTree((BTNode) node.getRight()); swap((BTNode) node,(BTNode) node.getLeft(), (BTNode) node.getRight()); } public static void swap(BTNode parent, BTNode left, BTNode right){ parent.setLeft(right); parent.setRight(left); } public static BTNode createTree() throws NonEmptyTreeException,InvalidPositionException { BTNode root = (BTNode) myTree.addRoot("ROOT"); BTNode P1 = (BTNode) myTree.insertLeft(root, "P1"); BTNode P3 = (BTNode) myTree.insertRight(root, "P3"); BTNode C1 = (BTNode) myTree.insertLeft(P1, "C1"); BTNode C2 = (BTNode) myTree.insertRight(P1, "C2"); BTNode C4 = (BTNode) myTree.insertLeft(P3, "C4"); BTNode C5 = (BTNode) myTree.insertRight(P3, "C5"); BTNode L1 = (BTNode) myTree.insertLeft(C1, "L1"); BTNode L2 = (BTNode) myTree.insertLeft(C2, "L2"); BTNode L5 = (BTNode) myTree.insertRight(C4, "L5"); return root; } } |

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.**

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

1 2 3 4 5 6 |
public static int depthNode(BTNode node) throws NonEmptyTreeException,InvalidPositionException, BoundaryViolationException { if (node == null || node == myTree.root) return 0; return 1 + depthNode((BTNode) node.getParent()); } |

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.**

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

1 2 3 4 5 6 7 |
public static int heightNode(BTNode node) throws NonEmptyTreeException, InvalidPositionException, BoundaryViolationException { if (node == null || node == myTree.root) return 0; return 1 + Math.max(heightNode((BTNode) node.getLeft()), heightNode((BTNode) node.getRight())); } |

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