recursive function in classic binary tree / predecessors

closed account (Nwb4iNh0)
Im writing recursive function in classic binary tree , to write the ID of all the nodes that are predecessors to the node, this is the progress so far



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


struct Node {
int ID;
Node *left, *right;
Node(const char id, Node* l, Node* r)
{ ID = id; left = l; right = r; }
};
  bool PrintPredecessors(Node* node, int id){
        if(node==NULL) return false;
        else if(node->ID == id) return true;
        if(PrintPredecessors(node->left,id)){
         cout<<node->ID<<"\n\n";
            return true;
       }   
       else if(PrintPredecessors(node->right)){
          cout<<node->ID<<"\n\n";
           return true;
       };  
       return false;
   }   
   
In C++, use nullptr instead of NULL.

As refactored, the code is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Node {
	int ID {};
	Node *left {}, *right {};
	Node(char id, Node* l, Node* r) : ID(id), left(l), right(r) {}
};

bool PrintPredecessors(Node* node, int id) {
	if (node == nullptr)
		return false;

	if (node->ID == id)
		return true;

	if (PrintPredecessors(node->left, id))
		return cout << node->ID << "\n\n", true;

	if (PrintPredecessors(node->right, id))
		return cout << node->ID << "\n\n", true;

	return false;
}


... and the C++ question is?

closed account (Nwb4iNh0)
the question is to write a recursive function to print the ID of all the nodes that are predecessors to the node with ID equal to id in classic binary tree not in BST
So, does it not work?
It appears as if it ought to.
Do you mean predecessors or ancestors? Predecessors are nodes whose ID is less than the current node's. Ancestors are nodes who are parents, grandparents, great-grandparents etc. of the node. You code appears to print ancestors.

Although it might work, your code is not efficient because it doesn't use the structure of the tree to help find the node you're looking for. For example, if ID > node->ID then there's no point in searching the left branch because you know that all those nodes are too small.
Topic archived. No new replies allowed.