Swift Coding Test Course, Finding the Parent of a Tree

In computer science, a tree is a type of hierarchical data structure and a kind of graph made up of nodes. In this course, we will solve an algorithm problem to find the parent node of a given node using Swift.

Problem Description

Write a function to find the parent node of a specific node in a given binary tree. The tree is represented as follows. 


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

You will be given a structure like the one above. Implement the `findParent` function to find the parent node of a specific node in the binary tree that uses this structure.

Function Signature


func findParent(root: TreeNode?, target: Int) -> Int?

Input

  • root: The root node of the binary tree (TreeNode? type)
  • target: The value of the node whose parent you want to find (Int type)

Output

The value of the parent node of the given node. If the given node does not exist or if the root node is the target, return nil.

Example

Assume there is a binary tree as follows:

            1
          /   \
         2     3
        / \   / \
       4   5 6   7

    findParent(root: rootNode, target: 5) ➔ 2
    findParent(root: rootNode, target: 1) ➔ nil
    findParent(root: rootNode, target: 8) ➔ nil

Algorithm Design

To find the parent node, we need to traverse the binary tree. We can use common traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). Here, we will adopt a method using DFS to recursively explore the tree.

DFS Traversal Method

  • If the current node is nil, end the search
  • Check if the value of the current node matches target
  • If matched, return the value of the current node’s parent
  • If not matched, recursively call on the left and right child nodes

Implementation

Now, let’s implement the findParent function based on the above algorithm.


func findParent(root: TreeNode?, target: Int) -> Int? {
    return findParentHelper(root, target: target, parent: nil)
}

private func findParentHelper(_ node: TreeNode?, target: Int, parent: TreeNode?) -> Int? {
    guard let node = node else { return nil } // If the current node is nil

    if node.value == target {
        return parent?.value // Return the parent node
    }

    // Search left child
    let leftResult = findParentHelper(node.left, target: target, parent: node)
    if leftResult != nil {
        return leftResult // Return if found parent in the left
    }

    // Search right child
    return findParentHelper(node.right, target: target, parent: node)
}

Test

Now, let’s test the implemented function to check if it works correctly.


let rootNode = TreeNode(value: 1)
rootNode.left = TreeNode(value: 2)
rootNode.right = TreeNode(value: 3)
rootNode.left?.left = TreeNode(value: 4)
rootNode.left?.right = TreeNode(value: 5)
rootNode.right?.left = TreeNode(value: 6)
rootNode.right?.right = TreeNode(value: 7)

print(findParent(root: rootNode, target: 5) ?? "nil") // 2
print(findParent(root: rootNode, target: 1) ?? "nil") // nil
print(findParent(root: rootNode, target: 8) ?? "nil") // nil

Conclusion

In this course, we implemented an algorithm to find the parent of a specific node in a binary tree using Swift. We applied the basic concept of DFS in the traversal problem of tree structures and learned how to write code.
Through these problems, you can enhance your understanding of trees and recursive thinking.

Additionally, I hope you build your skills by solving problems related to other properties of trees.