Swift Coding Test Course, Binary Tree

Hello! Today, we will solve a coding test problem related to binary trees. Binary trees are a data structure that appears frequently in many problems. A binary tree is a tree structure where each node can have a maximum of two children, allowing for various traversal methods. Our goal is to understand binary trees and utilize them to solve specific problems.

Problem Description

Given the following binary tree, write a function that traverses all nodes using DFS (Depth-First Search) and returns the values of the nodes as a list.

Problem Definition

func depthFirstTraversal(root: TreeNode?) -> [Int] {}

Input: The root node of the binary tree, root

Output: An integer array containing the values of the nodes from the DFS traversal

Example

Input:

        1
       / \
      2   3
     / \
    4   5
    

Output:

[1, 2, 4, 5, 3]

Definition of Binary Tree

A binary tree is a tree structure that can have two child nodes. Each node has a value, and binary trees are usually defined recursively. Since a node may be empty, the root node should be handled as nil.

Problem Solving Process

To solve this problem, we will explore the tree using the DFS method. DFS means Depth-First Search, which involves completely traversing one branch before moving on to the next. Below, we explain the process of tree traversal using DFS.

Step 1: Define Tree Node

First, we need to define a tree node. We will implement the TreeNode class to define a tree node.

    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?
        
        init(value: Int) {
            self.value = value
        }
    }
    

Step 2: Implement DFS Function

Now we will implement a function to traverse the binary tree using the DFS method. The priority is current node -> left child -> right child. We will perform this recursively.

    func depthFirstTraversal(root: TreeNode?) -> [Int] {
        guard let node = root else { return [] }
        
        // Add the current node's value to the array
        var result = [node.value]
        
        // Explore the left subtree
        result += depthFirstTraversal(root: node.left)
        
        // Explore the right subtree
        result += depthFirstTraversal(root: node.right)
        
        return result
    }
    

Step 3: Test and Validate

Now, we will create a binary tree to test the function we have implemented. We will use the example above to create the tree.

    let root = TreeNode(value: 1)
    let leftChild = TreeNode(value: 2)
    let rightChild = TreeNode(value: 3)
    let leftLeftChild = TreeNode(value: 4)
    let leftRightChild = TreeNode(value: 5)
    
    root.left = leftChild
    root.right = rightChild
    leftChild.left = leftLeftChild
    leftChild.right = leftRightChild
    
    let result = depthFirstTraversal(root: root)
    print(result)  // [1, 2, 4, 5, 3]
    

Conclusion

We have implemented a DFS algorithm to traverse binary trees. Through this problem, we were able to understand the structure of binary trees and the concept of DFS traversal. In Swift, trees can be easily traversed using recursion, and problems like this are common in coding tests, making it important to practice. In the next session, we will explore another algorithmic problem. Thank you!