CODEWITHSUNDEEP
c++binary-treecoutpostorder
Mayuri Harkishan
Mayuri Harkishan

Reputation: 9

Binary Tree - Print Left branches only - Using PostOrder Traverse - C++

Hi! I would like to know what can be the if statement's condition so all left branches of a binary tree could be printed using postorder traverse. 

template <class dataType>
void PrintLeft (BinaryTree <dataType> * bt) {

 if (!(bt == NULL))

 {

    //traverse left child

    PrintLeft (bt->left());

    //traverse right child

    PrintLeft (bt->right());

    //visit tree

    if(/*no idea what goes here*/)

    cout << bt->getData() <<"\t";

 }

}

Upvotes: 0

Views: 1039

Answers (4)

Sean Paul
Sean Paul

Reputation: 73

if(!bt->left()==NULL)
    cout << bt->left()->getData() << "\t";

Upvotes: 0

lrleon
lrleon

Reputation: 2648

I understand that you want to visit only the nodes that were seen from a left branch. Since it is postorder, you must visit them when you get back on the right branch. So, such as said by πάντα ῥεῖ, you can use a boolean flag indicating from which type of branch you have discovered the node.

So a possible way would be as follows:

using Node = BinaryTree <int>; // or another type supporting << operator

void printLeft(Node * root, bool from_left)
{
  if (root == nullptr) // empty tree?
    return; 

  printLeft(root->left, true); // this node must be visited in postorder
  printLeft(root->right, false); // this one must not be visited in postorder

  if (from_left) //  was root seen from a left arc?
    cout << root->getData() << "\t"; // visit only if was seen from a left branch
}

There is an ambiguity with the root. I assume that it must not be printed because it is not reached from a left branch (nor right too).

So the first call should be:

printLeft(root, false);

Just as verification, for this tree:

enter image description here

The algorithm produces as left postorder traversal the following sequence

0 1 4 3 8 9 12 11 16 18

Upvotes: 2

jagdish
jagdish

Reputation: 470

Try This One

 void leftViewUtil(struct node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;

    // If this is the first node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }

    // Recur for left and right subtrees
    leftViewUtil(root->left, level+1, max_level);
    leftViewUtil(root->right, level+1, max_level);
}

// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

// Driver Program to test above functions
int main()
{
    struct node *root = newNode(12);
    root->left = newNode(10);
    root->right = newNode(30);
    root->right->left = newNode(25);
    root->right->right = newNode(40);

    leftView(root);

    return 0;
}

Upvotes: 0

jagdish
jagdish

Reputation: 470

here goes code for postorder traversing

void postorder(BinaryTree *bt)
{
    if(bt!=NULL)
    {
        postorder(t->lp);
        postorder(t->rp);
        //No Code Goes Here
        cout<<bt->data<<"\t";
    }
}

Upvotes: 1

Related Questions