\n 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.\n<\/p>\n
\n Write a function to find the parent node of a specific node in a given binary tree. The tree is represented as follows.\n<\/p>\n
\nclass TreeNode {\n var value: Int\n var left: TreeNode?\n var right: TreeNode?\n \n init(value: Int) {\n self.value = value\n }\n}\n<\/code><\/pre>\nYou 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.<\/p>\n
Function Signature<\/h3>\n\nfunc findParent(root: TreeNode?, target: Int) -> Int?\n<\/code><\/pre>\nInput<\/h2>\n\n- root<\/strong>: The root node of the binary tree (TreeNode? type)<\/li>\n
- target<\/strong>: The value of the node whose parent you want to find (Int type)<\/li>\n<\/ul>\n
Output<\/h2>\n
\n 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<\/code>.\n<\/p>\nExample<\/h2>\n\nAssume there is a binary tree as follows:\n\n 1\n \/ \\\n 2 3\n \/ \\ \/ \\\n 4 5 6 7\n\n findParent(root: rootNode, target: 5) \u2794 2\n findParent(root: rootNode, target: 1) \u2794 nil\n findParent(root: rootNode, target: 8) \u2794 nil\n <\/code><\/pre>\n<\/div>\nAlgorithm Design<\/h2>\n
\n 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.\n<\/p>\n
DFS Traversal Method<\/h3>\n\n- If the current node is
nil<\/code>, end the search<\/li>\n- Check if the value of the current node matches
target<\/code><\/li>\n- If matched, return the value of the current node’s parent<\/li>\n
- If not matched, recursively call on the left and right child nodes<\/li>\n<\/ul>\n
Implementation<\/h2>\n
Now, let’s implement the findParent<\/code> function based on the above algorithm.<\/p>\n\nfunc findParent(root: TreeNode?, target: Int) -> Int? {\n return findParentHelper(root, target: target, parent: nil)\n}\n\nprivate func findParentHelper(_ node: TreeNode?, target: Int, parent: TreeNode?) -> Int? {\n guard let node = node else { return nil } \/\/ If the current node is nil\n\n if node.value == target {\n return parent?.value \/\/ Return the parent node\n }\n\n \/\/ Search left child\n let leftResult = findParentHelper(node.left, target: target, parent: node)\n if leftResult != nil {\n return leftResult \/\/ Return if found parent in the left\n }\n\n \/\/ Search right child\n return findParentHelper(node.right, target: target, parent: node)\n}\n<\/code><\/pre>\nTest<\/h2>\n
Now, let’s test the implemented function to check if it works correctly.<\/p>\n
\nlet rootNode = TreeNode(value: 1)\nrootNode.left = TreeNode(value: 2)\nrootNode.right = TreeNode(value: 3)\nrootNode.left?.left = TreeNode(value: 4)\nrootNode.left?.right = TreeNode(value: 5)\nrootNode.right?.left = TreeNode(value: 6)\nrootNode.right?.right = TreeNode(value: 7)\n\nprint(findParent(root: rootNode, target: 5) ?? \"nil\") \/\/ 2\nprint(findParent(root: rootNode, target: 1) ?? \"nil\") \/\/ nil\nprint(findParent(root: rootNode, target: 8) ?? \"nil\") \/\/ nil\n<\/code><\/pre>\nConclusion<\/h2>\n
\n 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.
\n Through these problems, you can enhance your understanding of trees and recursive thinking.\n<\/p>\n
Additionally, I hope you build your skills by solving problems related to other properties of trees.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"