logo CodeStepByStep logo

wordExists

Language/Type: C++ binary trees pointers recursion
Related Links:
Author: Marty Stepp (on 2016/11/11)

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: 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;
    ...
}
Type your C++ solution code here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.