0
\$\begingroup\$
eg:
   5
  / \
 3   4
/\   /\
7 8  9 1

should print: 5 3 7 8 4 9 1


#include <iostream>
include <stack>
using namespace std;`

class node{
public:
int val;
node* left;
node* right;
bool istraversed=false;
};


void printdfs(node* root){
stack<node*> s;
s.push(root);

while(!s.empty()){

    node *temp = s.top();
    if(temp->istraversed==false){
        cout<<temp->val<<" "; 
        temp->istraversed=true;
    }
    if(temp->left!=NULL){
        if(temp->left->istraversed==false){
            s.push(temp->left);
            continue;
        }
    }
    if(temp->right!=NULL){
        if(temp->right->istraversed==false){
            s.push(temp->right);
            continue;
        }
    }
    s.pop();
}    
}

int main() {

node* root;
root->val=1;
cout<<root->val<<",";

root->left->val = 2;
cout<<root->left->val<<",";
root->right->val = 3;
cout<<root->right->val<<",";

root->left->left->val=4;
cout<<root->left->left->val<<",";
root->left->right->val=5;
cout<<root->left->right->val<<",";
root->right->left->val=6;
root->right->right->val=7;
root->left->left->left->val=8;

printdfs(root);

return 0;

}

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Welcome to Code Review. Have you tested this code? How much have you tested it? Does it produce the output as you expect? \$\endgroup\$ – Simon Forsberg Apr 30 '16 at 10:02
  • \$\begingroup\$ Got it Simon. Sorry for not posting the result of running. It is giving me a segmentation fault currently. \$\endgroup\$ – SidShah Apr 30 '16 at 10:24
  • \$\begingroup\$ I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. \$\endgroup\$ – Simon Forsberg Apr 30 '16 at 10:31
  • \$\begingroup\$ Now working. Invite suggestions for improvement. \$\endgroup\$ – SidShah Apr 30 '16 at 13:22
  • \$\begingroup\$ Unfortunately it is important to us that the existing answer should not be invalidated by your edits. I would recommend you to post a new question instead. This question should remain closed. \$\endgroup\$ – Simon Forsberg Apr 30 '16 at 14:18
1
\$\begingroup\$

The order in which you're traversing the tree is a simple pre-order traversal. If you can use recursion, it's a much easier way to do this traversal:

void preorder(node *root) { 
    if (root == nullptr)
        return;
    std::cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

Other than that, your code currently has undefined behavior--in main you don't seem to be allocating any actual nodes for your tree. You're just taking an uninitialized pointer (root) and overwriting whatever happens to be in the memory it points at. To get something meaningful, you need to allocate your nodes.

I'd probably add a constructor to node to make construction a little easier:

struct node {
    int val;
    node *left, *right;

    node(int val) : val(val), left(nullptr), right(nullptr) {}
};

Then main would look something like this:

int main() { 
    node *root = new node(5);
    root->left = new node(3);
    root->left->left = new node(7);
    root->left->right = new node(8);
    root->right = new node(4);
    root->right->left = new node(9);
    root->right->right = new node(1);
    preorder(root);
    // possibly code here to delete the nodes of the tree.
}
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for pointing out how to initialize my tree with the constructors. The interviewer specifically asked not to use recursion, and hence I used a stack to traverse. \$\endgroup\$ – SidShah Apr 30 '16 at 10:19
  • \$\begingroup\$ So if I do root->val = 1 without allotting memory, I am curious what will happen? Will it not allot memory on its own? Or will it throw an error? Currently i am getting a segmentation fault. \$\endgroup\$ – SidShah Apr 30 '16 at 10:23
  • \$\begingroup\$ @SidShah: It's next to impossible to predict what will happen. it might appear to work, or it might dependably not work, or it might seem to work sometimes but not others, or... \$\endgroup\$ – Jerry Coffin Apr 30 '16 at 14:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.