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;
};