Write a function named wordExists that determines whether a particular word can be found along a downward path of consecutive nodes in a given tree of characters.
Your function accepts two parameters: a pointer to the root of a tree of chars, and the string to search for.
You must search from the root of the tree downward and return true when the supplied text is present and false otherwise.
For example, if a pointer named root points to the root of the tree drawn below, the call of wordExists(root, "crust") should return true because that path can be formed from the root downward to the "t" leaf.
The path need not start at the root, nor end at a leaf; your function would also return true for this tree if passed "rug", "us", "crab", "ran", "crust", "rust", "ugh", "czar", "zero", "zed", and so on.
The call of wordExists(root, "arc") should return false because "arc" cannot be formed in the right downward order.
Similarly, the call of wordExists(root, "cut") should return false because the nodes for 'c', 'u', and 't' are not immediate neighbors in the tree.
Your code should return as soon as an answer can be determined.
Prune your search and do not explore useless paths.
(c (r (a (b) (n)) (u (g (h)) (s / (t)))) (z (a / (r)) (e (r (o)) (d))))
Constraints:
You must implement your function recursively and without using loops.
Do not construct any new BinaryTreeNodeChar objects in solving this problem (though you may create as many pointer variables as you like).
Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).
Your function should not modify the tree's state; the state of the tree should remain constant with respect to your function.
Assume that you are using the BinaryTreeNodeChar structure as defined below:
struct BinaryTreeNodeChar {
char data;
BinaryTreeNodeChar* left;
BinaryTreeNodeChar* right;
};
