Skip to main content
added 177 characters in body
Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

The most efficient way of computing the height of a tree runs in linear time, and it looks like this:

class TreeNode:
    def __init__(self):
        self.left = None
        self.right = None


def get_tree_height(root):
    if root is None:
        return -1

    return max(get_tree_height(root.left), get_tree_height(root.right)) + 1


def main():
    a = TreeNode()
    b = TreeNode()
    c = TreeNode()
    d = TreeNode()
    e = TreeNode()

    a.left = b
    b.left = c
    c.right = d
    b.right = e

    print("Tree height:", get_tree_height(a))


if __name__ == "__main__":
    main()

If you need to compute the height of a tree which allows more than 2 children, just extend the algorithm to call itself at all the child nodes, and return the maximum of them.

Hope that helps.

The most efficient way of computing the height of a tree runs in linear time, and it looks like this:

class TreeNode:
    def __init__(self):
        self.left = None
        self.right = None


def get_tree_height(root):
    if root is None:
        return -1

    return max(get_tree_height(root.left), get_tree_height(root.right)) + 1


def main():
    a = TreeNode()
    b = TreeNode()
    c = TreeNode()
    d = TreeNode()
    e = TreeNode()

    a.left = b
    b.left = c
    c.right = d
    b.right = e

    print("Tree height:", get_tree_height(a))


if __name__ == "__main__":
    main()

Hope that helps.

The most efficient way of computing the height of a tree runs in linear time, and it looks like this:

class TreeNode:
    def __init__(self):
        self.left = None
        self.right = None


def get_tree_height(root):
    if root is None:
        return -1

    return max(get_tree_height(root.left), get_tree_height(root.right)) + 1


def main():
    a = TreeNode()
    b = TreeNode()
    c = TreeNode()
    d = TreeNode()
    e = TreeNode()

    a.left = b
    b.left = c
    c.right = d
    b.right = e

    print("Tree height:", get_tree_height(a))


if __name__ == "__main__":
    main()

If you need to compute the height of a tree which allows more than 2 children, just extend the algorithm to call itself at all the child nodes, and return the maximum of them.

Hope that helps.

Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

The most efficient way of computing the height of a tree runs in linear time, and it looks like this:

class TreeNode:
    def __init__(self):
        self.left = None
        self.right = None


def get_tree_height(root):
    if root is None:
        return -1

    return max(get_tree_height(root.left), get_tree_height(root.right)) + 1


def main():
    a = TreeNode()
    b = TreeNode()
    c = TreeNode()
    d = TreeNode()
    e = TreeNode()

    a.left = b
    b.left = c
    c.right = d
    b.right = e

    print("Tree height:", get_tree_height(a))


if __name__ == "__main__":
    main()

Hope that helps.