{{ message }}

Instantly share code, notes, and snippets.

# holyhan/lca.c

Last active Sep 30, 2018
Find lowest common ancestor for binary tree in C.
 #include #include #include 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 commented Sep 30, 2018 • edited

 `````` 14 / \ 7 9 / \ \ 5 4 3 ``````