{"id":34026,"date":"2024-11-01T09:23:13","date_gmt":"2024-11-01T09:23:13","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34026"},"modified":"2024-11-01T10:53:57","modified_gmt":"2024-11-01T10:53:57","slug":"c-coding-test-course-lowest-common-ancestor","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34026\/","title":{"rendered":"C# Coding Test Course, Lowest Common Ancestor"},"content":{"rendered":"

<\/p>\n

Hello, coding test applicants! Today we will delve deep into the problem of Lowest Common Ancestor (LCA). This problem is related to tree structures and requires a deep understanding of algorithms and data structures. We will also explore how to solve this problem using C#.<\/p>\n

Problem Definition<\/h2>\n

The problem is to find the lowest common ancestor of two nodes in a given binary tree. Given two nodes A and B, our goal is to find the deepest node that is an ancestor of both A and B.<\/p>\n

Example<\/h2>\n
\n        For instance, let's assume there is a binary tree as follows. \n\n              3\n             \/ \\\n            5   1\n           \/ \\ \/ \\\n          6  2 0  8\n            \/ \\\n           7   4\n\n        The lowest common ancestor of nodes 5 and 1 is 3.\n        The lowest common ancestor of nodes 5 and 2 is 5.\n        The lowest common ancestor of nodes 6 and 4 is 5.\n    <\/pre>\n
Approach to the Problem<\/h2>\n
    \n
  1. \n
    Understanding Tree Structure<\/h3>\n
    First, it is essential to understand the structure of a binary tree. Each node can have at most two children, and it can be divided into a left subtree and a right subtree. You should know how to traverse the tree to find nodes.<\/p>\n<\/li>\n
  2. \n
    Recursive Approach<\/h3>\n
    One of the main approaches is to search recursively. If the current node is either A or B, return the current node and explore the left and right subtrees to find the other node. If both are found, then the current node is the lowest common ancestor.<\/p>\n<\/li>\n
  3. \n
    Writing Tree Traversal Algorithm<\/h3>\n
    Now, we need to write the code in C# to implement the algorithm. In this process, we will incorporate recursion to navigate and verify nodes through the code.<\/p>\n<\/li>\n<\/ol>\n
    C# Code Implementation<\/h2>\n
    \n        \/\/ Definition of binary tree node class\n        public class TreeNode {\n            public int Value;\n            public TreeNode Left;\n            public TreeNode Right;\n\n            public TreeNode(int value) {\n                Value = value;\n                Left = null;\n                Right = null;\n            }\n        }\n\n        public class Solution {\n            public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {\n                \/\/ Base case: If root is null or root is p or q, return root\n                if (root == null || root == p || root == q) {\n                    return root;\n                }\n\n                \/\/ Search each node in the left and right subtrees\n                TreeNode left = LowestCommonAncestor(root.Left, p, q);\n                TreeNode right = LowestCommonAncestor(root.Right, p, q);\n\n                \/\/ If p and q are in different subtrees, the current node is LCA\n                if (left != null && right != null) {\n                    return root;\n                }\n\n                \/\/ If only one is found, return that node\n                return left ?? right;\n            }\n        }\n    <\/pre>\n
    Code Explanation<\/h2>\n
    This code is written to find the lowest common ancestor of two nodes in a given binary tree. Below are the descriptions of the key parts of the code:<\/p>\n
      \n
    1. \n
      TreeNode Class<\/h3>\n
      This class represents each node in the tree. It stores the value of each node, the left child node, and the right child node.<\/p>\n<\/li>\n
    2. \n
      LowestCommonAncestor Method<\/h3>\n
      This method is called recursively and checks if the current node is null or if it is p or q. It searches for p and q in the left and right subtrees, and if both are found in different subtrees, it returns the current node.<\/p>\n<\/li>\n<\/ol>\n
      Complexity Analysis<\/h2>\n
      The time complexity of this algorithm is O(N), where N represents the number of nodes in the tree. It is proportional to the need to traverse all nodes. The space complexity is O(H), where H represents the height of the tree. This corresponds to the depth of the recursion call stack.<\/p>\n
      Example Execution<\/h2>\n
      \n        \/\/ Example tree creation and finding LCA\n        TreeNode root = new TreeNode(3);\n        root.Left = new TreeNode(5);\n        root.Right = new TreeNode(1);\n        root.Left.Left = new TreeNode(6);\n        root.Left.Right = new TreeNode(2);\n        root.Right.Left = new TreeNode(0);\n        root.Right.Right = new TreeNode(8);\n        root.Left.Right.Left = new TreeNode(7);\n        root.Left.Right.Right = new TreeNode(4);\n\n        Solution solution = new Solution();\n        TreeNode p = root.Left; \/\/ Node 5\n        TreeNode q = root.Left.Right; \/\/ Node 2\n        TreeNode lca = solution.LowestCommonAncestor(root, p, q);\n        Console.WriteLine($\"Lowest Common Ancestor: {lca.Value}\"); \/\/ Outputs 5\n    <\/pre>\n
      Conclusion<\/h2>\n
      Today, we explored how to solve the lowest common ancestor problem using C#. This problem serves as a foundation for tackling various algorithmic challenges and requires an understanding of tree structure and recursive thinking. Through practice, I hope you will enhance your coding skills and increase your understanding of C# during this opportunity.<\/p>\n