Maximum Height Difference

This approach will create a function height(node) that will calculate the height of the node.

We will travel through all nodes, call the height function, and calculate the height difference between the left and right subtree and update the maximum height difference of the tree. We will traverse all nodes using traverse(node) function.

Algorithm:

• Defining the height(node) function:
  • If the node is the empty node, return 0.
  • Now we will recursively call the height functions for both left and right children. Define two variables leftHeight and rightHeight to store the height of left and right subtrees.
  • Set leftHeight as height(left subtree of the node).
  • Set rightHeight as height(right subtree of the node).
  • curHeight is a variable to store the value of the current node.
  • Set curHeight as the maximum of leftHeight and rightHeight. 
  • We will increment curHeight by 1.
  • Return curHeight.

• We will traverse the tree using a function traverse(node), which returns the maximum height difference in the subtree whose root is node.
• Defining traverse(node) function:
  • If node is an empty node, return 0.
  • Set lHeight as height(left child of the node).
  • Set rHeight as height(right child of the node).
  • Declare a variable curDiff to store the height difference of the current node.
  • Set curDiff as absolute difference of lHeight and rHeight.
  • Now traverse to the left and right child.
  • Declare maxDiffLeft and maxDiffRight to store the maximum height difference in the left subtree and right subtree.
  • Set maxDiffLeft as traverse(left child of node).
  • Set maxDiffRight as traverse(right child of node).
  • Set maxDiff as the maximum of maxDiffLeft, maxDiffRight, and curDiff.
  • Return maxDiff.

• Store the maximum height difference of the tree in a variable ans.
• Set ans as traverse(root)
• Return the variable ans.

As we have discussed in the previous approach, we are traversing through each node and calculating the heights of subtrees, and updating the maximum height difference.

In this approach, we will implement the height of the node as well as the maximum height difference using a single function.

We will calculate the height of the subtrees and compare the maximum height difference using a recursive function recFunc(node). The function recFunc(node) will return an array containing two values of height of the tree, and maximum height difference in the subtree with node as root.

Algorithm:

• We will define a function recFunc(node) with parameters node representing the current node and return an array containing the height of the current node and max Difference between left and right subtree. This function will calculate the height and also compare the maximum difference of the heights.
  • If the node is the empty node, return [0,0] as the height of an empty tree is zero.
  • We will define leftSubTree and rightSubTree arrays to store the height and max difference in the left and right subtree, respectively.
  • To calculate the leftSubTree, we will set leftSubTree as recFunc(left child of node).
  • Similarly,to calculate the rightSubTree we will set rightSubTree as rec(right child of node).
  • leftSubTree[0] represents the height of the left subtree, and leftSubTree[1] represents the maximum height difference in the left subtree.
  • Declare a variable curDiff representing the height difference for the current node.
  • Set curDiff as absolute difference of leftSubTree[0] and rightSubTree[0].
  • Now we will compare and update the maxDiff as the maximum of curDiff, the maximum difference in the left subtree, and the maximum difference in the right subtree.
  • Set maxDiff as maximum of curDiff, leftSubTree[1] and rightSubTree[1].
  • Declare a variable curHeight to store the height of the node.
  • Set curHeight as maximum of leftSubTree[0] and rightSubTree[0].
  • Increment curHeight by 1.
  • Now, we will return the current height and updated maxDiff.
  • We will return [curHeight, maxDiff].

• We will declare a variable ans to store the height and maximum height difference of the given tree.
• Set ans as recFunc(root, ans)
• Return ans[1] corresponding to maximum height difference in the given tree.

In this approach, we will use a queue to traverse through all the nodes in a level order manner, and we will store all nodes in a stack. We will also declare a HashMap to store the height of each node. While removing the nodes from the stack, it will follow the reverse order, and we will compute the heights of the bottom level first and store them in HashMap and use these values to calculate the height of their parents. Then we will compare the height difference for each node and will update the maxDiff value accordingly.

Algorithm:

• We will first declare a queue que to traverse through all nodes iteratively in a level order manner.
• We will also define a stack named nodes to store the pointers of all nodes, which we will use later to calculate the height of all nodes.
• Insert root into the queue que.
• While que is not empty, do the following:
  • Set cur as the front node of the que.
  • Remove cur from the que.
  • Insert cur in the nodes.
  • If the left child of cur is not an empty node, insert it into que.
  • If the right child of cur is not an empty node, insert it into que.
• Now, the stack nodes contain the pointers of all nodes.
• We will declare a hashMap named heightMap to store each node’s heights and declare a variable maxDiff to store the maximum height difference.
• While the stack nodes is not empty, do the following:
  • Set cur as the top node of the nodes.
  • Remove cur from the nodes.
  • leftHeight is the height of the left subtree of cur, and rightHeight is the height of the right subtree of cur.
  • We will check if the left child of cur is an empty node.
    • Set leftheight to 0.
  • Otherwise, we will check if the left child of cur is not an empty node.
    • Set the leftHeight as heightmap[left child of cur].
  • Do the same steps for the right child also and calculate rightHeight accordingly
  • The height of the left subtree and right subtree is calculated. We will update maxDiff as the maximum of maxDiff and the absolute difference of leftHeight and rightHeight.
  • Store the height of the cur node in heightMap. Set heightMap[cur] as the maximum of leftHeight and rightHeight. Increment heightMap[cur] by 1.
• Now, we compared the height difference for all nodes.
• Return the variable maxDiff.