Swift Coding Test Course, Understanding Trees

1. Problem Description

In this course, we will enhance our understanding of tree structures using Swift and solve algorithmic problems based on it.
Specifically, we will address the following problem:

Problem: Calculate the Height of a Binary Tree

Write a function to calculate the height of a given binary tree. The height of a binary tree is defined as the length of the longest path from the root node to a leaf node.
The height of a node starts at 0, with leaf nodes having a height of 0.

2. Example

When given the following binary tree, 

        1
       / \
      2   3
     / \
    4   5

The height of this tree is 2, as the leaf nodes 4 and 5 are two steps away from the root node 1.

3. Approach

This problem can be solved recursively, and the main ideas are as follows:

  1. Define a recursive function to calculate the height of the current node’s left and right child nodes.
  2. Compare the heights of each child node to find the maximum.
  3. The height of the root node is 1 plus the maximum of the left and right child heights.

4. Implementation

Below is the function for calculating the height of a binary tree implemented in Swift: 

struct TreeNode {
    var value: Int
    var left: TreeNode?
    var right: TreeNode?
}

func height(of node: TreeNode?) -> Int {
    guard let node = node else {
        return -1 // A null node has a height of -1.
    }
    let leftHeight = height(of: node.left)
    let rightHeight = height(of: node.right)
    return max(leftHeight, rightHeight) + 1
}

5. Code Explanation

The function height(of node: TreeNode?) is called recursively.
First, it returns -1 if the node is nil (null), indicating that there is no height for the path including leaf nodes.
After calculating the heights of the left and right children, it selects the larger of the two values and adds 1 to return the height of the current node.

6. Time Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the tree.
It takes this time because we have to visit every node once.

7. Additional Tasks

Users can practice more through the following additional tasks:

  • Write a function to check if a specific value exists in the given tree.
  • Write a function to return all the leaf nodes of the binary tree.
  • Implement level order tree traversal to visit all nodes in level order.

8. Conclusion

In this course, we have learned about the concept of binary trees and the basic height calculation algorithm.
Trees play a very important role in data structures, and understanding them is essential for solving algorithmic problems.
Tree-related problems are frequently encountered in coding tests, so practice enough to improve your skills.