Find Node in Binary Tree - Binary Tree
In this article, we will see how to find the node with a given key in a binary tree, using a recursive solution. Because we're talking about a binary tree, not a binary search tree, we cannot take advantage of the binary search tree property.
The idea is to start at the root of the tree, and check if the key of root is equal to the key we're looking for. If that's the case, we return root. Else we try to find the key in the left subtree. If we don't find it, we then try the right subtree. If we again fail to find it, this means that there is no node with the key we're searching, so we return null.
With that in mind, here's the function that tries to find the node with a given key in a binary tree, and returns that node, or returns null if there is no node with such key.
Node *findNode(Node *root, int key) {
if (root == nullptr) return nullptr;
if (root->key == key) return root;
Node *found = findNode(root->left, key);
if (found != nullptr) return found;
return findNode(root->right, key);
}
Time complexity
The time complexity is O(n) (where n is the size of the tree) because in the worst case the node we're looking for is not in the tree and we will check the key of every single node in the tree. See the video for more detail.
Space complexity
The space complexity is O(h) (where h is the height of the tree) because this is a function that calls itself recursively, so the call stack grows with each call, and in the worst case there will be as many calls as the height of the tree, which means that the space taken is O(h).