Two binary tree problems for this week.

99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

My accepted code can be found here

This problem looked verrry hard when I first saw it and took me a lot of time to think. While it turns out it’s not difficult at all.

“Two elements in a BST are swapped” is actually equivalent to “two elements in a sorted array are swapped”, and finding the two element swapped in an original sorted array should be relatively easy. The only difference here is we need to record the mistaken node during the inorder searching, and at last swap the value of them.

And for identifying the mistaken element in a originally sorted array, the only thing we do is to find two adjacent elements where first is larger than the second. At the first time, we pick the larger element to swap, at the second time, we pick the smaller element to swap.

Recover(root: Node):
    let prev: Node = null
    let a: Node = null
    let b: Node = null
    Search(root, prev, a, b)
    swap(a.value, b.value)

Search(now: Node, prev: Node, a: Node, b: Node):
    if now == null then return
    Search(now.left, prev, a, b)
    if prev != null and prev.value > now.value then
        if a == null then a = prev; b = now
        else b = now
    prev = now
    Search(now.right, prev, a, b)

The time complexity is O(n) and space is O(1) as request.

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

My accepted code can be found here

This problem views a binary tree as an acyclic graph, and find the path with maximum sum of node value. And this problem should be solved by recursion and postorder search (dynamic programming if you like).

Since the value of the node could be negative, so the induction case should be calculated carefully.


MaximumPathSum(node: Node):
    let res = minimum value of integer
    Search(node)
    return res

Search(node: Node):
    if node == null then return 0
    let leftMax = Search(node.left)
    let rightMax = Search(node.right)
    let n = node.value
    res = max(res, n, n + leftMax + rightMax, n + leftMax, n + rightMax)
    return max(n, n + leftMax, n + rightMax)

The return value of “Search” is the maximum sum of the path starting from the node. And the postorder search calculate the result(global maximum) by trying to combining the left path, the right path and the node itself.

The time complexity is O(n) and space is O(1).