Skip to content

Instantly share code, notes, and snippets.

@holyhan
Last active September 30, 2018 08:48
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save holyhan/44b6dc76d9f633af579527d42f49f095 to your computer and use it in GitHub Desktop.
Save holyhan/44b6dc76d9f633af579527d42f49f095 to your computer and use it in GitHub Desktop.
Find lowest common ancestor for binary tree in C.
#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;
}
@holyhan
Copy link
Author

holyhan commented Sep 30, 2018

        14
      /    \
    7       9
  /   \       \
5     4        3

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment