iOS Interview - Leetcode 104. Maximum Depth of Binary Tree

June 16, 2024 • 2 min read • #swift, #interview, #leetcode

Leetcode: 104. Maximum Depth of Binary Tree

Primary idea: Use DFS to calculate max depth of left and right node from the parent node.
Time Complexity: O(n)
Space Complexity: O(n)

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

extension TreeNode {
    public func printTree() {
        printTreeHelper(self, "", true)
    }

    private func printTreeHelper(_ node: TreeNode?, _ prefix: String, _ isLeft: Bool) {
        guard let node = node else { return }

        let arrow = isLeft ? "┣━━" : "┗━━"
        let branch = isLeft ? "┃  " : "   "

        print(prefix + arrow + " " + "\(node.val)")

        printTreeHelper(node.left, prefix + branch, true)
        printTreeHelper(node.right, prefix + branch, false)
    }
}

func maxDepth(_ root: TreeNode?) -> Int {
    guard let root else {
        return 0
    }

    return max(maxDepth(root.left), maxDepth(root.right)) + 1
}


// [3,9,20,null,null,15,7]
let root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right?.left = TreeNode(15)
root1.right?.right = TreeNode(7)
root1.printTree()
//┣━━ 3
//┃  ┣━━ 9
//┃  ┗━━ 20
//┃     ┣━━ 15
//┃     ┗━━ 7
print(maxDepth(root1)) // 3

// [1,null,2]
let root2 = TreeNode(1)
root2.right = TreeNode(2)
root2.printTree()
//┣━━ 1
//┃  ┗━━ 2
print(maxDepth(root2)) // 2