C++

Forum

 
 
What is this binary tree outputting?

Apr 22, 2020 at 11:23pm
XboxOne2019 (82)
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?
Apr 23, 2020 at 12:33am
dutch (2548)
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';
}
Edit & run on cpp.sh

Last edited on Apr 23, 2020 at 12:44am
Apr 23, 2020 at 1:23am
XboxOne2019 (82)
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.