0
0
DSA Goprogramming~20 mins

Height of Binary Tree in DSA Go - Practice Problems & Challenges

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
Binary Tree Height Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
What is the height of this binary tree?

Consider the following binary tree structure and code to calculate its height. What is the printed height?

DSA Go
package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func height(root *Node) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    root.Left.Left = &Node{Val: 4}
    root.Left.Right = &Node{Val: 5}
    fmt.Println(height(root))
}
A4
B2
C3
D5
Attempts:
2 left
💡 Hint

Height is the number of nodes on the longest path from root to a leaf.

❓ Predict Output
intermediate
2:00remaining
Output of height function on a skewed tree

What is the output of the height function for this skewed binary tree?

DSA Go
package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func height(root *Node) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func main() {
    root := &Node{Val: 1}
    root.Right = &Node{Val: 2}
    root.Right.Right = &Node{Val: 3}
    root.Right.Right.Right = &Node{Val: 4}
    fmt.Println(height(root))
}
A0
B3
C1
D4
Attempts:
2 left
💡 Hint

Height counts nodes along the longest path from root to leaf.

🧠 Conceptual
advanced
1:00remaining
What does the height of an empty tree return?

In the height function for a binary tree, what is the returned height when the input root node is nil?

A0
B-1
C1
Dnil
Attempts:
2 left
💡 Hint

Think about the base case for recursion when there is no node.

🔧 Debug
advanced
2:30remaining
Why does this height function give wrong output?

Consider this height function code. It returns wrong height for some trees. What is the bug?

DSA Go
func height(root *Node) int {
    if root == nil {
        return -1
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight > rightHeight {
        return leftHeight
    }
    return rightHeight
}
AIt should return 0 for nil nodes instead of -1
BBoth B and C
CIt should add 1 to the max height of children before returning
DIt returns -1 for nil nodes and does not add 1 for current node height
Attempts:
2 left
💡 Hint

Check base case and how height is calculated from children.

🚀 Application
expert
3:00remaining
Calculate height of a binary tree with iterative approach

Which code snippet correctly calculates the height of a binary tree using an iterative method (level order traversal)?

A
func height(root *Node) int {
    if root == nil {
        return 0
    }
    queue := []*Node{root}
    height := 0
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        height++
    }
    return height
}
B
func height(root *Node) int {
    if root == nil {
        return 0
    }
    stack := []*Node{root}
    height := 0
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        height++
    }
    return height
}
C
func height(root *Node) int {
    if root == nil {
        return 0
    }
    queue := []*Node{root}
    height := 1
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
        height++
    }
    return height
}
D
func height(root *Node) int {
    if root == nil {
        return 0
    }
    var queue []*Node
    queue = append(queue, root)
    height := 0
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        height += 1
    }
    return height
}
Attempts:
2 left
💡 Hint

Height is number of levels. Use queue to process nodes level by level.