Successor of a node in a Binary Search Tree - Swift

Question

Trying to solve the successor for a nod in a binary tree s.t. the tree

has the following successors: for 8 -> 10, 10 -> 12 and 14 -> 20

However, for 10 I'm returning nil (and, indeed for 14 I'm returning nil).

My algorithm is:

func inorderSucc(_ node: Node? = nil) -> Node? {
    if (node == nil) {
        return nil
    } else {
        if let rhn = node?.right {
            return leftMostChild(rhn)
        } else {
            var q = node
            var x = node?.parent
            while (x != nil && x!.left != q) {
                q = x
                x = x?.parent
            }
            return x
        }
    }
}

func leftMostChild(_ n: Node) -> Node? {
    var node = n
    while (node.left != nil) {
        node = node.left!
    }
    return node
}

Calling a tree:

class Node : CustomStringConvertible, Hashable{
    var hashValue : Int { return data}
    static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs.data == rhs.data
    }

    var data : Int
    var left : Node?
    var right : Node?
    var parent : Node? = nil
    var description: String {
        return String(data) + (left?.description ?? "") + (right?.description ?? "")
    }

    init(_ data: Int) {
        self.data = data
    }

    func insert(_ data: Int) {
        if (data < self.data){
            if let lhs = left {
                lhs.insert(data)
            }
            else {
                let lhNode = Node(data)
                lhNode.parent = self
                left = lhNode
            }
        }
        else {
            if let rhs = right {
                rhs.insert(data)
            }
            else {
                let rhNode = Node(data)
                rhNode.parent = self
                right = rhNode
            }
        }
    }
}

inorderSearch is:

func inorderSearch (_ node: Node, _ data: Int) -> Node? {
    if (node.data == data) {return node}
    else {
        if let lft = node.left {
            return inorderSearch(lft, data)
        }

        if let rht = node.right {
            return inorderSearch(rht, data)
        }

    }

    return nil
}

And I insert the nodes as follows:

let gfg = Node(20)
gfg.insert(8)
gfg.insert(4)
gfg.insert(12)
gfg.insert(10)
gfg.insert(14)
gfg.insert(22)
print (gfg)
inorderSucc(inorderSearch(gfg, 8))
inorderSucc(inorderSearch(gfg, 10))
inorderSucc(inorderSearch(gfg, 14))

With the last three lines returning 10, nil and nil respectively. What's going wrong?

Answer 1

The issue stems from your search function. Think of what's happening if it doesn't find the actual number on the leftmost branch (child node(s) of the left node of the left node etc. ... of the root node). A possible correction would be to check for nil while exploring the left hand side, and then proceed to the right hand side of the subgraph as well.

func inorderSearch (_ node: Node, _ data: Int) -> Node? {
    if (node.data == data) {return node}
    else {
        if let lft = node.left, let found = inorderSearch(lft, data) {
            return found
        } else if let rht = node.right, let found = inorderSearch(rht, data) {
            return found
        } else {
            return nil
        }
    }
}

This code suppose that you don't have any preconception of what kind of graph this is. Otherwise, you could also check if the searched number is greater or lesser than your current node's value, and search in the left side or the right side accordingly.