BinaryTree

BinaryTree.swift

// MARK: Data Structure

public class BinaryTreeNode<Element: Comparable> {
    
    weak var parent:BinaryTreeNode?
    
    var leftNode:BinaryTreeNode?
    var payload:Element
    var rightNode:BinaryTreeNode?
    
    // MARK: - Initialise
    init(withPayload payload: Element) {
        self.payload = payload
    }

}

// MARK: - CREATE AND WRITE

extension BinaryTreeNode {
    
    /// Add payload to tree
    /// - Parameter element: An element which is having constrain of `Comparable`
     func add(payloadFromRoot element: Element) {
        /*  Root node: `parent`
         *  Parent Node(i.e Root Node): It's node which doesn't have parent node
         *
         */
        if let parentExist = self.parent {
            print("Since \(parentExist), It's not the root node of tree");
            return
        }
        self.append(payload: element)
    }
    
    private func append(payload:Element) {
        
        if self.payload > payload {
            if let leftNode = leftNode {
                leftNode.append(payload: payload)
            } else {
                let newNode = BinaryTreeNode(withPayload: payload)
                newNode.parent = self
                leftNode = newNode
            }
        } else {
            if let rightNode = rightNode {
                rightNode.append(payload: payload)
            } else {
                let newNode = BinaryTreeNode(withPayload: payload)
                newNode.parent = self
                rightNode = newNode
            }
        }
    }
    
}

// MARK: -  TRAVERSAL (Depth First Traversal) AND READ

extension BinaryTreeNode {
    // In-order
    // Left Node -> Value -> Right Node
    class func traverseInOrder(fromNode node: BinaryTreeNode?) {
        
        guard let unwarappedNode = node else {
            return
        }
        
        BinaryTreeNode.traverseInOrder(fromNode: unwarappedNode.leftNode)
        print(unwarappedNode.payload)
        BinaryTreeNode.traverseInOrder(fromNode: unwarappedNode.rightNode)
    }
    
    // Pre-order
    // Value -> LeftNode -> Right Node
     class func traversePreOrder(fromNode node: BinaryTreeNode?) {
        
        guard let unwarappedNode = node else {
            return
        }
        
        print(unwarappedNode.payload)
        BinaryTreeNode.traversePreOrder(fromNode: unwarappedNode.leftNode)
        BinaryTreeNode.traversePreOrder(fromNode: unwarappedNode.rightNode)
    }

    // Post-order
    // LeftNode -> rightNode -> Value
    class func traversePostOrder(fromNode node:BinaryTreeNode?) {
        
        guard let unwarappedNode = node else {
            return
        }
        
        BinaryTreeNode.traversePostOrder(fromNode : unwarappedNode.leftNode)
        BinaryTreeNode.traversePostOrder(fromNode : unwarappedNode.rightNode)
        print(unwarappedNode.payload)
    }
}

// MARK: -  TRAVERSAL(Breadth First Traversal) AND READ

extension BinaryTreeNode {
    
    class func traversLevelOrder(fromNode node: BinaryTreeNode?) {
        guard let unwrappedNode = node else {
            return
        }
        
        // first in first out(i.e Queue) Data Structure
        var queue = [BinaryTreeNode]()
        queue.append(unwrappedNode)
        
        // Iterating over until fifo become empty
        while !queue.isEmpty {
            let firstNode = queue.removeFirst()
            queue.append(firstNode)
            
            if let leftNodeOfFirstNode = firstNode.leftNode {
                queue.append(leftNodeOfFirstNode)
            }
            
            if let rightNodeOfFirstNode = firstNode.rightNode {
                queue.append(rightNodeOfFirstNode)
            }
        }
    }
}


// MARK: -  SEARCH

extension BinaryTreeNode {
    
    func search(forPayload payload :Element) -> BinaryTreeNode? {
        
        // If we find the payload
        guard payload != self.payload else {
            return self
        }
        
        if self.payload > payload {
            guard let left = leftNode else {
                return nil
            }
            return left.search(forPayload: payload)
        } else {
            guard let right = rightNode else {
                return nil
            }
            return right.search(forPayload: payload)
        }
    }
}

extension BinaryTreeNode {
    
    // Finding Minimum value
    func minimumValue() -> Element {
        //Check if left node exist, If Yes, try finding it's minimum else it contain the minimum value
        if let left = leftNode {
            return left.minimumValue()
        }else {
            return payload
        }
    }
    
    
    // Finding Maximum value.
    func maximumValue() -> Element {
        //Check if right node exist, If Yes, try finding it's maximum else it contain the maximum value
        if let right = rightNode {
            return right.maximumValue()
        } else {
            return payload
        }
    }
    
    
    //Finding minimum node of the tree.
    func minimum() -> BinaryTreeNode {
        //Check if left node exist, If Yes, try finding it's minimum else it is minimum node
        if let left = leftNode {
            return left.minimum()
        }else {
            return self
        }
    }
    
    
    //Finding maximum node of the tree.
    func maximum() -> BinaryTreeNode {
        //Check if right node exist, If Yes, try finding it's maximum else  it is minimum node
        if let right = rightNode {
            return right.maximum()
        }else {
            return self
        }
    }
    
    //Height of B-Tree
    func height() -> Int {
        // Check if leftNode and RightNode are nil, It's the root node and it's height is zero
        if leftNode == nil && rightNode == nil {
            return 0
        }
        // Try finding maximum of leftNode and rightNode
        return 1 + max(leftNode?.height() ?? 0, rightNode?.height() ?? 0)
    }
}