10. Deepest Node in a Binary Tree
Question: Find the Deepest Node in a Binary Tree.
For example, you should return 4.
1
/ \
2 3
/
4Hints:
- You need to compare the node’s height,
- To browse the nodes, use a DFS.
Solution:
fileprivate func deepestNode(node: BinaryNode<Int>) -> (BinaryNode<Int>, Int) {
// 1.
var deepest: (BinaryNode<Int>, Int) = (node, 0)
// 2.
if let left = node.left {
deepest = deepestNode(node: left)
}
if let right = node.right {
// 3.
let deepestRight = deepestNode(node: right)
if deepestRight.1 > deepest.1 {
deepest = deepestRight
}
}
// 4.
return (deepest.0, deepest.1 + 1)
}Explanations:
1. Let’s define the deepest node from the current node.
var deepest: (BinaryNode<Int>, Int) = (node, 0)2. If the current node has a left child, let’s define the deepest from the result of the recursive call with its left child.
if let left = node.left {
deepest = deepestNode(node: left)
}3. If the current node has a right child, let’s compare the current deepest with the result of the recursive call from the right child and keep the deepest.
let deepestRight = deepestNode(node: right)
if deepestRight.1 > deepest.1 {
deepest = deepestRight
}4. Return the deepest and increment the current height.
return (deepest.0, deepest.1 + 1)Complexity:
- Time Complexity: As we will browse all nodes once, the time complexity is linear O(n) n number being the number of nodes,
- Space Complexity: As we recurse on the tree, the time complexity will be due to the call stack; the time complexity will be O(h), where h is the height of the tree.
Test-cases:
public func testDeepestNode() {
let n1 = BinaryNode<Int>(value: 1)
let n2 = BinaryNode<Int>(value: 2)
let n3 = BinaryNode<Int>(value: 3)
let n4 = BinaryNode<Int>(value: 4)
n1.left = n2
n1.right = n3
n2.left = n4
assert(deepestNode(node: n1).0.value == 4, "deepestNode 1 not equal")
}Follow-up:
Find the Kth deepest node.
<< More Interview Questions | Data Structures and Algorythms >>
