What is this binary tree outputting?

We had a test question about what this function was outputting for the binary tree and even the smartest student in the class only got a 3/10. The test is over and he will not be telling us the answer as this is how he always is. I was going to ask on here what is the output of this? I ran it and it seemed like it was printing both sides of the binary tree and then the entire thing.

This is the tree we were given. I cant draw the lines, but just imagine them.

h
d l

b f j n

a c e g i k m o

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 struct Node
{
  char val;
  Node *rChild, *lChild;
};

void ptr(Node *p)
{
  if(p == NULL)
  {
    return;
   ptr(p->lChild);
   ptr(r->rChild);
   cout<<" \n- ";
   ptrAgain(p);
}

 void ptrAgain(Node *p)
{
  if(p == NULL)
  {
    return;
    ptrAgain(p->lChild);
    cout<<p->val;
    ptrAgain(p->rChild);
}

  int main()
{
  ptr(head);  //head of tree structure 
}


This is what we put as the output:

-g 
-fg
-efg
-defg
-cdefg
-bcdefg
-abcdefg
-o
-no
-mno
-lmno
-klmno
-jklmno
-ijklmno
-abcdefghijklmno


This was wrong so I am curious what the final answer is?
It won't print anything since it won't compile. But assuming the errors (unmatched opening braces) are not in the original then it's actually pretty easy.

       h
   d       l

 b   f   j   n

a c e g i k m o

ptr is calling ptrAgain postorder.
The postorder of the nodes is:

a c b e g f d i k j m o n l h

ptrAgain prints the subtree rooted at each of those nodes inorder, so:

-a
-c
-a b c
-e
-g
-e f g
-a b c d e f g
-i
-k
-i j k
-m
-o
-m n o
-i j k l m n o
-a b c d e f g h i j k l m n o


EDIT: This seems to confirm that the above is correct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>

struct Node
{
    char val;
    Node *rChild = nullptr, *lChild = nullptr;
    Node(char v) : val(v) {}
};

void ptrAgain(Node *p);

void ptr(Node *p)
{
    if (!p)
        return;
    ptr(p->lChild);
    ptr(p->rChild);
    std::cout << "\n-";
    ptrAgain(p);
}

void ptrAgain(Node *p)
{
    if (!p)
        return;
    ptrAgain(p->lChild);
    std::cout << p->val << ' ';
    ptrAgain(p->rChild);
}

void insert(Node*& node, char val)
{
    if (!node)
        node = new Node(val);
    else
        insert(val < node->val ? node->lChild : node->rChild, val);
}

int main()
{
    Node *head = nullptr;
    for (char val: std::string("hdlbfjnacegikmo"))
        insert(head, val);
    ptr(head);
    std::cout << '\n';
}

Last edited on
ah ok. I see now. It was tripping us all up. It was a timed 30 min question and we all wernt sure. Thanks for your help.
Topic archived. No new replies allowed.