Depth First search using postorder traversal recursion produces unexpected output

Question

This recursive function has a problem and produces unexpected output.

It should go through the binary tree and search for a given node that holds data x using preorder depth first traversal.

After it finds the node it should return. I have two other functions for preorder and inorder traversal which work fine. This one does not stop when it finds the node, but keeps going up the callstack till it reaches the root and returns the root value of the tree. I have included all the functions below. The first one is the one that isn't working right.

//this one does not work
template<typename T>
inline typename BST<T>::Node* BST<T>::depth_first_postorder_s(Node* root,T x)
{
            //if root is null
            if (!root)
                return nullptr;
             depth_first_postorder_s(root->left,x);
             depth_first_postorder_s(root->right,x);
             if (root->data == x) {
                 return root;
             }
}

template<typename T>
inline typename BST<T>::Node* BST<T>::depth_first_inorder_s(Node* root, T x)
{
            //if root is null
            if (!root)
                return nullptr;
              depth_first_inorder_s(root->left,x);
              if (root->data == x) {
                  return root;
              }
             depth_first_inorder_s(root->right,x);
}

template<typename T>
inline typename BST<T>::Node* BST<T>::depth_first_preorder_s(Node* root,T x)
{
            //if root is null
            if (!root)
                return nullptr;
            if (root->data == x) {
                return root;
            }
             depth_first_preorder_s(root->left,x);
             depth_first_preorder_s(root->right,x);
}

All of the functions seem to be invalid — in case of non-null root if root->data does not equal x, they don't return anything. — Daniel Langr

Faruk Hossain Faruk Hossain · Accepted Answer · 2019-11-19T11:30:00

All of the functions seem to be invalid in your code. But therefore as you say that first one is giving you wrong value so modification of that function should be -

inline typename BST<T>::Node* BST<T>::depth_first_postorder_s(Node* root,T x)
{


             //if root is null
             if (!root)
                 return nullptr;
             Node *lft = depth_first_postorder_s(root->left,x);
             Node *rgt = depth_first_postorder_s(root->right,x);
             if (root->data == x) {
                 return root;
             } else if(lft != nullptr) {
                 return lft;
             } else { 
                 return rgt;
             }
}

Here you need to return the node to the previous recursion call which is equal to the x.

Other functions should be implemented similarly.

Depth First search using postorder traversal recursion produces unexpected output

1 Answers