Find the height of an element in a binary tree, iteratively

Question

How to find the height of an element in a binary tree? In an iterative approach.

If the element was 22 in the following binary tree its height would be 2. Should I first find the height of the binary tree, then start with that height and as I go one node lower, decrement it?

If you have an answer, feel free to write it in pseudocode or in any programming language you want. Thank you.

Answer 1

Do a level order traversal on the tree and keep a variable to track the depth of the current node.

1. Height of the tree will be the depth of the deepest node.
2. If you find the node you are looking for store that in a variable
3. In the end subtract the depth of the node from the height of the tree.

Code:

class BinaryTreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def setChildren(self, left, right):
        self.left = left
        self.right = right

def heightOfNode(root, searchValue):
    queue, depth, maxDepth = [], None, 0
    if (root != None):
        queue.append((root, 1))
        maxDepth = 1
    while len(queue) > 0:
        node, nodeDepth = queue.pop(0)
        if (node.left != None):
            queue.append((node.left, nodeDepth + 1))
        if (node.right != None):
            queue.append((node.right, nodeDepth + 1))
        if (node.val == searchValue):
            depth = nodeDepth
        maxDepth = max(nodeDepth, maxDepth)
    return maxDepth - depth

if __name__=='__main__':
    node14 = BinaryTreeNode(14)
    node22 = BinaryTreeNode(22)
    node2 = BinaryTreeNode(2)
    node1 = BinaryTreeNode(1)
    node5 = BinaryTreeNode(5)
    node20 = BinaryTreeNode(20)
    node30 = BinaryTreeNode(30)
    node4 = BinaryTreeNode(4)
    node17 = BinaryTreeNode(17)
    node50 = BinaryTreeNode(50)
    node40 = BinaryTreeNode(40)

    node14.setChildren(node2, node22)
    node2.setChildren(node1, node5)
    node22.setChildren(node20, node30)
    node5.setChildren(node4, None)
    node20.setChildren(node17, node50)
    node30.setChildren(None, node40)

    print(heightOfNode(node14, 22))

output:

2