Tree || LeetCode || Swift

102. Binary Tree Level Order Traversal

    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        
        if(root == nil){
            return []
        }
        var queue:[TreeNode?] = [root]
        var result: [[Int]] = []

            while !queue.isEmpty{
                var level: [Int] = []
                let levelCount = queue.count

         for _ in 0..<levelCount {
             print(queue.count)
            let node = queue.removeFirst()
            level.append(node?.val ?? 0)
            if let left = node?.left {
                queue.append(left)
            }
            if let right = node?.right {
                queue.append(right)
            }
        }
                    result.append(level)
            }

        
        return result
    }

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

199. Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

  func rightSideView(_ root: TreeNode?) -> [Int] {
        var result:[Int] = [Int]()
        f(root, 0 , &result )
        return result
    }

    func f(_ root:TreeNode?,_ level:Int,_ result:inout [Int]){
        if(root == nil){
            return
        }

        if(level == result.count){
            result.append(root?.val ?? 0)
        }
        f(root?.right , level + 1, &result)
        f(root?.left , level + 1, &result)
    }

144. Binary Tree Preorder Traversal/inorder Traversal

  func preorderTraversal(_ root: TreeNode?) -> [Int] {
            guard let root = root else { return [] }
             return [(root.val)]  + preorderTraversal(root.left)  +  preorderTraversal(root.right) 
   
    }

  func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }

        return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
    }

101. Symmetric Tree

    func isSymmetric(_ root: TreeNode?) -> Bool {
        return checkSymmetric(root?.left , root?.right)
    }

   private func checkSymmetric(_ leftNode:TreeNode?,_ rightNode:TreeNode?) -> Bool{
       if let leftNode = leftNode , let rightNode = rightNode {
           return  ( leftNode.val == rightNode.val && checkSymmetric(leftNode.left, rightNode.right) && checkSymmetric(leftNode.right, rightNode.left))
       }else{
           return leftNode == nil && rightNode == nil
       }
   }

543. Diameter of Binary Tree

    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
         var result = 0
        maxDepth(root, &result)
        return result
    }

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

        let leftMax = maxDepth(root.left, &result)
        let rightMax = maxDepth(root.right, &result)
        
        result = max(result, leftMax + rightMax)

        return max(leftMax, rightMax) + 1
    }

111. Minimum Depth of Binary Tree

   // O(d) time | O(d) space
    func minDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        var queue = [root], depth = 1
        
        while !queue.isEmpty {
            let count = queue.count
            for _ in 0..<count {
                let removed = queue.removeFirst()
                if removed.left == nil && removed.right == nil { return depth }
                if let left = removed.left { queue.append(left) }
                if let right = removed.right { queue.append(right) }
            }
            depth += 1
        }
        
        return depth
    }

100. Same Tree

func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    
       guard p != nil || q != nil else {return true}  
    
        guard let p = p , let q = q else {return false}
    
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }

112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

 func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        guard let root = root else {return false}

        if root.val == targetSum && root.left == nil && root.right == nil
        {
            return true
        }
        return hasPathSum(root.left , targetSum - root.val) || hasPathSum(root.right , targetSum - root.val)
    }

98. Validate Binary Search Tree

 func isValidBST(_ root: TreeNode?) -> Bool {
        func checkBST(_ node:TreeNode?, _ low:Int, _ high:Int) -> Bool{
            guard let node = node else {return true}
            if !(low < node.val && node.val < high) {return false}
     return checkBST(node.left, low, node.val) && checkBST(node.right, node.val, high)

        }
        return checkBST(root,Int.min, Int.max)
    }

226. Invert Binary Tree

func invertTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else {return nil}
        (root.left, root.right) = (invertTree(root.right), invertTree(root.left))
        return root
    }

124. Binary Tree Maximum Path Sum

    func maxPathSum(_ root: TreeNode?) -> Int {
        var maximumValue:Int = Int.min
         maxRec(root, &maximumValue)
         return  maximumValue
    }

    func maxRec(_ root:TreeNode?,_ maximumValue: inout Int) -> Int{
        if(root == nil){
            return 0
        }

        var leftNode =  max(0, maxRec(root?.left, &maximumValue ))
        var rightNode =  max(0,maxRec(root?.right, &maximumValue ))
            
        maximumValue = max(maximumValue , leftNode + rightNode + (root?.val ?? 0))
        return max(leftNode, rightNode) + (root?.val ?? 0)
    }