Last active
September 30, 2018 08:48
-
-
Save holyhan/44b6dc76d9f633af579527d42f49f095 to your computer and use it in GitHub Desktop.
Find lowest common ancestor for binary tree in C.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <memory.h> | |
typedef struct TreeNode { | |
int value; | |
struct TreeNode *leftNode; | |
struct TreeNode *rightNode; | |
} TreeNode; | |
TreeNode * | |
find_node(TreeNode *root, TreeNode *node1, TreeNode *node2) | |
{ | |
// If root is NULL, return NULL | |
if (root == NULL) { | |
return NULL; | |
} | |
// If root is not node1 or node 2, then root is returned | |
if (root == node1 || root == node2) { | |
return root; | |
} | |
// To traverse root left node and right node | |
TreeNode *leftNode = find_node(root->leftNode, node1, node2); | |
TreeNode *rightNode = find_node(root->rightNode, node1, node2); | |
// If node1 and node2 are around root, then root is returned | |
if (leftNode && rightNode) { | |
return root; | |
} else if (leftNode == NULL && rightNode == NULL) { | |
return NULL; | |
} else {// Otherwise, left node or right node is returned | |
return leftNode ? leftNode : rightNode; | |
} | |
} | |
void | |
set_leaf_node(TreeNode *root, TreeNode *leftNode, TreeNode *rightNode) { | |
if (root == NULL) { | |
return; | |
} | |
root->leftNode = leftNode; | |
root->rightNode = rightNode; | |
} | |
TreeNode * | |
new_node(int value) { | |
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode)); | |
memset(root, 0, sizeof(TreeNode)); | |
root->value = value; | |
return root; | |
} | |
int main(int argc, char const *argv[]) { | |
TreeNode *root = new_node(14); | |
TreeNode *node7 = new_node(7); | |
TreeNode *node9 = new_node(9); | |
TreeNode *node5 = new_node(5); | |
TreeNode *node4 = new_node(4); | |
TreeNode *node3 = new_node(3); | |
set_leaf_node(root, node7, node9); | |
set_leaf_node(node7, node5, node4); | |
set_leaf_node(node9, NULL, node3); | |
TreeNode *public_node = find_node(root, node5, node3); | |
printf("Common parent node:%d\n", public_node->value); | |
return 0; | |
} |
Author
holyhan
commented
Sep 30, 2018
•
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment