logo CodeStepByStep logo

hasPath

Language/Type: C++ binary trees pointers recursion
Author: Marty Stepp (on 2016/06/16)

Write a member function named hasPath that could be added to the BinaryTree class. The function accepts integers start and end as parameters and returns true if a path can be found in the tree from start down to end. In other words, both start and end must be element data values that are found in the tree, and end must be below start, in one of start's subtrees; otherwise the function returns false. If start and end are the same, you are simply checking whether a single node exists in the tree with that data value. If the tree is empty, your function should return false.

For example, suppose a BinaryTree variable named tree stores the following elements. The table below shows the results of several various calls to your function:

           67
        /      \
    80            52
  /    \         /
16     21      99
      /
    45
Call Result Reason
tree.hasPath(67, 99) true path exists 67 -> 52 -> 99
tree.hasPath(80, 45) true path exists 80 -> 21 -> 45
tree.hasPath(67, 67) true node exists with data of 67
tree.hasPath(16, 16) true node exists with data of 16
tree.hasPath(52, 99) true path exists 52 -> 99
tree.hasPath(99, 67) false nodes do exist, but in wrong order
tree.hasPath(80, 99) false nodes do exist, but there is no path from 80 to 99
tree.hasPath(67, 100) false end of 100 doesn't exist in the tree
tree.hasPath(-1, 45) false start of -1 doesn't exist in the tree
tree.hasPath(42, 64) false start/end of -1 and 45 both don't exist in the tree

An empty tree does not contain any paths, so if the tree is empty, your method should return false. You should not assume that your tree is a binary search tree (BST); its elements could be stored in any order.

Constraints: Your member function should not modify the tree's state; the state of the tree should remain constant with respect to your function. Do not construct any new BinaryTreeNode objects in solving this problem (though you may create as many BinaryTreeNode* pointer variables as you like). Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).

Write the member function as it would appear in BinaryTree.cpp. You do not need to declare the function header that would appear in BinaryTree.h. Assume that you are adding this method to the BinaryTree class as defined below:

class BinaryTree {
private:
    BinaryTreeNode* root;   // NULL for an empty tree
    ...
    
public: 
    your code goes here;
};

struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    ...
}
Type your solution here:


This is a member function problem. Submit a member function that will become part of an existing C++ class. You do not need to write the complete class, just the member function described in the problem.

You must log in before you can solve this problem.


Log In

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.