Lowest Common Ancestor in Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCA for given nodes in a binary tree

What is the output of the program when finding the Lowest Common Ancestor (LCA) of nodes 5 and 1 in the given binary tree?

DSA Go

package main

import "fmt"

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}

    p := root.Left      // Node with Val 5
    q := root.Right     // Node with Val 1

    lca := lowestCommonAncestor(root, p, q)
    fmt.Println(lca.Val)
}

A 3

B 5

C 1

D 6

💡 Hint

Think about the lowest node that has both nodes 5 and 1 as descendants.

The Lowest Common Ancestor of nodes 5 and 1 is the root node 3 because 3 is the lowest node in the tree that has both 5 and 1 as descendants.

❓ Predict Output

intermediate

Output of LCA for nodes in the same subtree

What is the output of the program when finding the Lowest Common Ancestor (LCA) of nodes 6 and 2 in the given binary tree?

DSA Go

package main

import "fmt"

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}

    p := root.Left.Left   // Node with Val 6
    q := root.Left.Right  // Node with Val 2

    lca := lowestCommonAncestor(root, p, q)
    fmt.Println(lca.Val)
}

A 2

B 6

C 5

D 3

💡 Hint

Both nodes are in the left subtree of the root.

Nodes 6 and 2 are both children of node 5, so the LCA is node 5.

🔧 Debug

advanced

Identify the error in LCA function implementation

What error will occur when running this LCA function code?

DSA Go

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

A Panic due to nil pointer dereference if p or q is nil

B No error, works correctly

C Infinite recursion causing stack overflow

D Compilation error due to missing return statement

💡 Hint

Check how the function handles nil and base cases.

The function correctly handles nil root and base cases by returning root when it matches p or q. It will not cause runtime or compile errors.

❓ Predict Output

advanced

Output when one node is ancestor of the other

What is the output of the program when finding the Lowest Common Ancestor (LCA) of nodes 5 and 6 in the given binary tree?

DSA Go

package main

import "fmt"

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}

    p := root.Left      // Node with Val 5
    q := root.Left.Left // Node with Val 6

    lca := lowestCommonAncestor(root, p, q)
    fmt.Println(lca.Val)
}

A 6

B 3

C 2

D 5

💡 Hint

If one node is ancestor of the other, the ancestor is the LCA.

Node 5 is an ancestor of node 6, so the LCA is node 5.

🧠 Conceptual

expert

Understanding LCA algorithm behavior with missing nodes

If one of the nodes (p or q) is not present in the binary tree, what will the LCA function return?

A Returns the node that is present if found, otherwise nil

B Returns nil because both nodes must be present to find LCA

C Returns the root node always regardless of presence

D Causes a runtime error due to nil pointer dereference

💡 Hint

Consider how the function returns when it finds p or q and when it doesn't.

The function returns the node if found; if only one node is present, it returns that node as the LCA. If neither is found, it returns nil.