Swift Breadth-First Search

Swift Breadth-first search

You only need to remove your tempNode variable and just always use the head of the queue:

func breadthFirstSearch(_ data: Int) -> Node? {
    var queue = [self]

    while let head = queue.first {
        queue.remove(at: 0)

        if (head.data == data) {
          return head
        }

        if let lft = head.left {
            queue.append(lft)
        }

        if let rht = head.right {
            queue.append(rht)
        }
    }
    return nil
}

Your original implementation would actually iterate over the first (root) node twice. I have also removed the unnecessary double checking in the beginning.

Now you can also see the difference against Depth First Search:

func depthFirstSearch(_ data: Int) -> Node? {
    var stack = [self]

    while let head = stack.popLast() {
        if (head.data == data) {
            return head
        }

        if let lft = head.left {
            stack.append(lft)
        }

        if let rht = head.right {
            stack.append(rht)
        }
    }
    return nil
}

Breadth First Search: Thread 1: Swift runtime failure: force unwrapped a nil value

Your problem is in how the dequeue function in otherQueue works. You are adjusting the pointers before returning data, which results in returning nil after removing the head from a queue with one entry.

Try something like...

func dequeue() -> T? {
    if self.head?.data == nil { return nil  }
    let result = head?.data
    if let nextItem = self.head?.next {
        head = nextItem
    } else {
        head = nil
    }
    return result
}

Also, you shouldn't be calling dequeue in while(!otheryQueue.isEmpty || otheryQueue.dequeue() != nil).

Performing Breadth First Search recursively

(I'm assuming that this is just some kind of thought exercise, or even a trick homework/interview question, but I suppose I could imagine some bizarre scenario where you're not allowed any heap space for some reason [some really bad custom memory manager? some bizarre runtime/OS issues?] while you still have access to the stack...)

Breadth-first traversal traditionally uses a queue, not a stack. The nature of a queue and a stack are pretty much opposite, so trying to use the call stack (which is a stack, hence the name) as the auxiliary storage (a queue) is pretty much doomed to failure, unless you're doing something stupidly ridiculous with the call stack that you shouldn't be.

On the same token, the nature of any non-tail recursion you try to implement is essentially adding a stack to the algorithm. This makes it no longer breadth first search on a binary tree, and thus the run-time and whatnot for traditional BFS no longer completely apply. Of course, you can always trivially turn any loop into a recursive call, but that's not any sort of meaningful recursion.

However, there are ways, as demonstrated by others, to implement something that follows the semantics of BFS at some cost. If the cost of comparison is expensive but node traversal is cheap, then as @Simon Buchan did, you can simply run an iterative depth-first search, only processing the leaves. This would mean no growing queue stored in the heap, just a local depth variable, and stacks being built up over and over on the call stack as the tree is traversed over and over again. And as @Patrick noted, a binary tree backed by an array is typically stored in breadth-first traversal order anyway, so a breadth-first search on that would be trivial, also without needing an auxiliary queue.

How to pass a class as a function argument?

Some initial cautions

Passing types in Swift is nearly always a Bad Smell. Swift does not treat metatypes like types.

Moreover, your addValue can never be written as specified. You cannot pass a Container into it or out of it, because Container is a generic protocol, which cannot be used as a type (e.g. when specifying a function parameter or function return type).

You can make generic classes that conform to a generic protocol, thus guaranteeing that you can push to an instance of any such class. But you cannot further unify them under some single head, because they are both generics and might be resolved differently.

Having said all that, we can probably make a pretty good approach to your idea, as I shall now demonstrate.

Revising your protocol and classes

Thinking about the general sort of thing you're trying to do, I suspect you're after an architecture somewhat like this:

protocol Pushable : class {
    associatedtype T
    init(_ t:T)
    var contents : [T] {get set}
    func push(_ t:T)
}

final class Stack<TT> : Pushable {
    init(_ t:TT) { self.contents = [t]}
    var contents = [TT]()
    func push(_ t:TT) {
        self.contents.append(t)
    }
}

final class Queue<TT> : Pushable {
    init(_ t:TT) { self.contents = [t]}
    var contents = [TT]()
    func push(_ t:TT) {
        self.contents.insert(t, at:0)
    }
}

I've called your Container by the name Pushable just because the ability to call push is all we have in common right now. You'll notice that I've added an init to the Pushable protocol; that's so that we have a way of resolving a Pushable generic. Whatever value we initialize a Pushable with, its type becomes its generic parameterized type; at the moment, that instance goes into the contents and further instances can be pushed, though I'll show later how to change that.

So now we can say stuff like this:

let stack = Stack("howdy")
stack.push("farewell")
let queue = Queue(1)
queue.push(2)

The joy of where clauses

Okay, now let's return to your desire to push an arbitrary value to an arbitrary Pushable. The way to express that is to use Pushable, not as a passed type or a return type, but as a constraint on a generic. That is something we are allowed to use a generic protocol for:

func push<TTT,P>(_ what:TTT, to pushable: P) 
    where P:Pushable, P.T == TTT  {
        pushable.push(what)
}

A factory method and passing a metatype

But you'll no doubt notice that I still haven't supplied a function with the ability to make a Queue-or-Stack. To do that, we would indeed need to pass a metatype. Aha, but I've given Pushable an init requirement! So now we can do it:

func createStackOrQueue<TTT,P>(_ what:TTT, type pushableType: P.Type) -> P
    where P:Pushable, P.T == TTT {
       return P.init(what)
}

let stack = createStackOrQueue("howdy", type:Stack.self)

That isn't identically what you were trying to do, but perhaps it's close enough to get you going.

Factory method, passing only metatypes

If you really insist on passing metatypes around, let's change init so that it too takes a metatype:

protocol Pushable : class {
    associatedtype T
    init(_ t:T.Type)
    var contents : [T] {get set}
    func push(_ t:T)
}

final class Stack<TT> : Pushable {
    init(_ t:TT.Type) { self.contents = [TT]()}
    var contents = [TT]()
    func push(_ t:TT) {
        self.contents.append(t)
    }
}

final class Queue<TT> : Pushable {
    init(_ t:TT.Type) { self.contents = [TT]()}
    var contents = [TT]()
    func push(_ t:TT) {
        self.contents.insert(t, at:0)
    }
}

Now we can write a generic factory function very close to what you were originally after, where both the Pushable (Stack or Queue) and the content type are expressed as metatypes:

func createPushable<TTT,P>(_ whatElementType:TTT.Type, type pushableType: P.Type) -> P 
    where P:Pushable, P.T == TTT {
        return P.init(TTT.self)
}

I can't say I approve of that sort of thing, but at least you can see how it's done.

Something very close to your original idea

And now I think we can make something very close to your original conception, where we say whether we want a stack or a queue along with something to push onto it! Ready?

func createPushable<TTT,P>(type pushableType: P.Type, andPush element:TTT) -> P
    where P:Pushable, P.T == TTT {
        let result = P.init(type(of:element).self)
        result.push(element)
        return result
}

And here's how to call it:

let stack = createPushable(type:Stack.self, andPush:"howdy")

DFS in Swift not terminating

When you remove the last item from the stack, you're removing the items you just pushed on. In your bfs implementation, remove first will grab the intended parent node regardless of the fact that you do it at the end of the loop, because you add the children to the end of the queue. You should move the operation to remove the expanded node from your stack to before you push new nodes on.

Purpose of typealias

1. typealias is literally for creating an "alias" (i.e. another name) for a type. You are not creating a new type, just another name for an existing type. From the Language Reference:

   Type aliases do not create new types; they simply allow a name to refer to an existing type.

   Therefore, once you declared the typealias, Graph and [String: [String]] now refers to the same type. An extension on Graph is equivalent to an extension on [String: [String]].

2. For your desired behaviour, you need to create a new type. For a Graph, I think a struct would be appropriate:

   struct Graph {
       ...
   }
   

   The Graph struct can then contain (or, encapsulate) a private property of type [String: [String]],

   private var adjacencyDictionary: [String: [String]]
   

   and you should write methods that accesses, and (optionally) mutates the graph. e.g. getNode(withName:), getNeighboursOfNode(withName:), addNode, addEdge etc.

   You should not use a typealias here, because a graph is not a [String: [String]]. For example, the following [String: [String]] is not a (valid) graph:

   ["a": ["b"]]
   

Updating a binary tree using a pointer

For me the main issue as I mentioned in the comments was with these line of code

fileprivate(set) var root: Node
    fileprivate let nullLeaf = Node()
    
    public init() {
        root = nullLeaf
    }

Root is currently pointing to a nullLeaf which has the following properties:

key = nil
leftChild = nil
self.rightChild = nil
self.parent = nil

I wasn't sure how your insert function was implemented but when I used my insert implementation, this updated the root's properties to the following:

key = nil
leftChild = node
self.rightChild = nil
self.parent = nil

Now when you run your search function which starts at the root:

func search(key: T, f: (inout Node) -> Void) {
        search(key: key, node: &root, f:  f)
    }

    fileprivate func search(key: T, node: inout Node, f: (inout Node) -> Void) {
        if !node.isNullLeaf {
            if let nodeKey = node.key {
                /// When a node is found, pass by reference as an
                /// argument to a closure so that it retains the 
                /// connection to the node when it's being update.
                if key == nodeKey {
                    f(&node)
                } else if key < nodeKey {
                    guard node.leftChild != nil else {
                        return
                    }
                    search(key: key, node: &node.leftChild!, f: f)
                } else {
                    guard node.rightChild != nil else {
                        return
                    }
                    search(key: key, node: &node.rightChild!, f: f)
                }
            }
        }
    }

if let nodeKey = node.key { is false based on the above root attributes and so it does go into your block where the logic and completion handler gets executed.

Changes and Implementation

Since your main question to answer is

But can't seem to figure out why the original code isn't updating a
node by pointer.

I am using my insertion implementation of a Binary Search Tree even though you mentioned Binary Tree as the main purpose is to show the pointer working.

Here is what I updated to your code:

TreeNode - no changes to your code

// No change to your original code
public class TreeNode<T: Comparable>: Equatable {
    public typealias Node = TreeNode<T>
    
    var key: T?
    var leftChild: Node?
    var rightChild: Node?
    fileprivate weak var parent: Node?
    
    var isNullLeaf: Bool {
        return key == nil && isLeaf
    }
    
    var isLeaf: Bool {
        return rightChild == nil && leftChild == nil
    }
    
    public init(key: T?, leftChild: Node?, rightChild: Node?, parent: Node?) {
        self.key = key
        self.leftChild = leftChild
        self.rightChild = rightChild
        self.parent = parent
        
        self.leftChild?.parent = self
        self.rightChild?.parent = self
    }
    
    /// Null leaf
    public convenience init() {
        self.init(key: nil, leftChild: nil, rightChild: nil, parent: nil)
    }
    
    static public func == <T>(lhs: TreeNode<T>, rhs: TreeNode<T>) -> Bool {
        return lhs.key == rhs.key
    }
}

Tree - minor changes and some additions, I have added comments

public final class Tree<T: Comparable> {
    public typealias Node = TreeNode<T>
    
    // root starts off as nil
    fileprivate(set) var root: Node?
    
    // I don't make use of this
    //fileprivate let nullLeaf = Node()
    
    // No initialization of root
    public init() {
        //root = nullLeaf
    }
    
    // No change to your code except to safely evaluate root
    func search(key: T, f: (inout Node) -> Void) {
        if var root = root {
            search(key: key, node: &root, f:  f)
        }
    }
    
    // No change to your code here
    fileprivate func search(key: T, node: inout Node, f: (inout Node) -> Void)
    {
        if !node.isNullLeaf {
            if let nodeKey = node.key {
                /// When a node is found, pass by reference as an argument
                /// to a closure so that it retains the connection to the node
                /// when it's being update.
                if key == nodeKey {
                    f(&node)
                } else if key < nodeKey {
                    guard node.leftChild != nil else {
                        return
                    }
                    search(key: key, node: &node.leftChild!, f: f)
                } else {
                    guard node.rightChild != nil else {
                        return
                    }
                    search(key: key, node: &node.rightChild!, f: f)
                }
            }
        }
    }
    
    // My insert implementation
    public func insert(key: T) {
        if let root = insertInternal(key, currentNode: root)
        {
            self.root = root
        }
    }
    
    // My insert recursion implementation
    private func insertInternal(_ data: T, currentNode: Node?) -> Node?
    {
        if currentNode == nil
        {
            let newNode = Node()
            newNode.key = data
            return newNode
        }
        
        if let currentData = currentNode?.key, data > currentData
        {
            currentNode?.rightChild
                = insertInternal(data, currentNode: currentNode?.rightChild)
            return currentNode
        }
        
        currentNode?.leftChild
            = insertInternal(data, currentNode: currentNode?.leftChild)
        
        return currentNode
    }
    
    // My implementation ofLevel order / Breadth first traversal
    // to display values
    func printLevelOrder()
    {
        print("\n** PRINTING BST IN LEVEL ORDER (BFS) ** ")
        
        var queue: [Node] = []
        
        if let root = root
        {
            queue.append(root)
        }
        
        while !queue.isEmpty
        {
            let currentNode = queue.removeFirst()
            
            if let currentData = currentNode.key
            {
                print(currentData)
                
                if let left = currentNode.leftChild
                {
                    queue.append(left)
                }
                
                if let right = currentNode.rightChild
                {
                    queue.append(right)
                }
            }
        }
    }
}

Test class - no much changes

// No change to your code here except display function
class Test<T: Comparable> {
    private(set) var tree = Tree<T>()
    
    func insert(key: T) {
        tree.insert(key: key)
    }
    
    func update(for node: T, with newNode: T) {
        tree.search(key: node) { foundNode in
            foundNode.key = newNode
        }
    }
    
    // Just added a display
    func display() {
        tree.printLevelOrder()
    }
}

Finally here is the main

Test 1 - simple with 1 node

print("Test 1")
var test = Test<Int>()
print("Inserting 10")
test.insert(key: 10)
print("Updating 10 with 8")
test.update(for: 10, with: 8)
test.display()

Output

Test 1
Inserting 10
Updating 10 with 8

** PRINTING BST IN LEVEL ORDER (BFS) ** 
8

As you can see the exchange of values has happened successfully with the pointer

Test 2 - a little more complex tree with many nodes

print("\n\nTest 2")
test = Test<Int>()
print("Inserting 5")
test.insert(key: 5)
print("Inserting 11")
test.insert(key: 11)
print("Inserting 4")
test.insert(key: 4)
print("Inserting 7")
test.insert(key: 7)
print("Inserting 17")
test.insert(key: 17)
print("Current tree before update")
test.display()

This should give us a binary search tree like this:

And printing the BFS traversal shows us this:

Test 2
Inserting 5
Inserting 11
Inserting 4
Inserting 7
Inserting 17
Current tree before update

** PRINTING BST IN LEVEL ORDER (BFS) ** 
5
4
11
7
17

Now Let's try to change the value of 7 with 16 which is done with the pointer

print("Updating 7 with 16")
test.update(for: 7, with: 16)
print("Current tree after update")
test.display()

The output is as expected with the value of 7 and swapped with 16

Updating 7 with 16
Current tree after update

** PRINTING BST IN LEVEL ORDER (BFS) ** 
5
4
11
16
17

Ofcourse, after this swap, the tree is no longer a Binary Search Tree but I think you can see the pointer working well with the above tweaks.

---

Related Topics