C++

Forum

 
Constructing binary tree

learner999 (102)
Hello everyone,
I need to construct a binary tree with the 0 and 1 values based on a condition starting from root node 0.
I have an array arr=[ 4 6 1] . If the numbers in the array is greater then 3, I need to add 0 and 1 to right and left otherwise I need to add 0.
For this array for example, what I need to obtain
Output :
0 // Root
/ \
0 1 // Checks 4 in the array
/ \ / \
0 1 0 1 // Checks 6 in the array
| | | |
0 0 0 0 // Checks 1 in the array
How can I construct this tree, thank you so much. I followed some examples in the internet but they mostly insert the values from a given array without any condition. Thank you so much for your helps
Last edited on
learner999 (102)
Any idea?
AbstractionAnon (6954)
We didn't see your attempts to solve this problem yourself and so we cannot correct mistakes you didn't made and answer questions you didn't ask. To get help you should do something yourself and get real problems with something. If your problem is "I don't understand a thing", then you should go back to basics and study again. As it is impossible to find derivative of function without knowledge in arithmetic, you cannot do more complex tasks in programming without clear understanding of basics
jonnin (11437)
you may also need to either give us the original problem or make sure the result of your test case is valid. it says add zero if < 3 but your 1 didn't do anything. It doesn't say where to add the zero.
most online trees will insert less left, greater right which allows rapid searching of the tree, or they will insert at the bottom, if not ordered for searches (unusual).

seeplus (6591)
How can I construct this tree,


Well really the first question is - Can you construct any tree with left and right nodes? If you can, then it's just a matter of choosing whether to add a node left or right. If you can't construct a tree then that's a different issue.

If you're attempted a tree class, then post the code here so that we can have a look and provide advice and guidance.
Last edited on
lastchance (6980)
Are you sure that you have paraphrased your problem correctly?

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
48
49
50
 
#include <iostream>
#include <vector>
using namespace std;

struct node
{
   int data;
   node *left = 0, *right = 0;
};

/*
void insert( node *n, bool both )
{
   if ( n->left   ) insert( n->left , both );
   else             n->left  = new node{ 0 };

   if ( n->right  ) insert( n->right, both );
   else if ( both ) n->right = new node{ 1 };
}
*/

void insert( node *n, bool both )
{
   if ( n->left || n->right )    // Not at bottom of tree - don't add nodes!
   {
      if ( n->left   ) insert( n->left , both );
      if ( n->right  ) insert( n->right, both );
   }
   else
   {
      n->left  = new node{ 0 };
      if ( both ) n->right = new node{ 1 };
   }
}

void output( node *n )
{
   if ( !n ) return;
   output( n->left );
   cout << n->data;
   output( n->right );
}

int main()
{
   vector<int> A = { 6, 4, 1 };
   node *root = new node{ 0 };
   for ( int e : A ) insert( root, e > 3 );
   output( root );
}


00001000101
Last edited on
seeplus (6591)
Do you mean this (assuming I've understood the requirement)?

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
 
#include <iostream>
#include <vector>

struct Node {
	bool data {};
	Node *left {}, *right {};

	Node() {}
	Node(int d) : data(d) {}
};

void insert(Node* n, bool cond) {
	if (n->left)
		insert(n->left, cond);
	else
		n->left = new Node;

	if (n->right)
		insert(n->right, cond);
	else if (cond)
		n->right = new Node { cond };
}

void output(const Node* n) {
	if (n) {
		output(n->left);
		std::cout << n->data;
		output(n->right);
	}
}

int main() {
	const std::vector arr { 6, 4, 1 };
	auto root { new Node };

	for (const auto& e : arr)
		insert(root, e > 3);

	output(root);
}



00001000101


with output in in-order traversal order.
Last edited on
learner999 (102)
Millions of thanks @lastchance and @seeplus. Yes, you understood the question well and answered. In fact, I had tried to do something similar to @lastchance's olution. However, I had received an error and I received the same error when I debug @lastchance's solution. For the line ,
node *root = new node{ 0 };
I receive ;
it is not possible to convert initializer list to a node . My confusion was coming from the same place, can I convert a list like {0} or {0,1} for example when we check the value 4 in the array, is it possible to convert those values to nodes ?

How can we get rid of this error ?
Thank you so much

lastchance (6980)
I received the same error when I debug @lastchance's solution. For the line ,
node *root = new node{ 0 };
I receive ;
it is not possible to convert initializer list to a node .


If necessary, you can write values for all data members in the initialisation of the struct:
new node{ 0, 0, 0 };
or, alternatively, create an explicit one- or three-parameter constructor for node. However, the likelihood is that you are using a C++11 compiler and the behaviour in this respect changed between C++11 and C++14 (as you can try for yourself now on cpp.sh). See "Aggregate member initialization" at https://en.wikipedia.org/wiki/C++14

Obviously, you could use any later C++ standard as well. Currently we're at C++20, although compiler support for that is a bit hit and miss, so I prefer not to assume that is available.
Last edited on
learner999 (102)
Thank you so much @lastchance for your answers and thank you so much @seeplus for your solution. I understoo well and solved the problem.
learner999 (102)
Actually I would like to ask one more question to @seeplus and I would be very happy if you can answer. In your solution, the point I can not understand how it decides it will make two branches 0 and 1 or just 0. For example the first value in the array is 6 which corresponds 1 in terms of boolean , is not it How does it insert the other branch which holds 0?

The second question, maybe @lastchance can also answer it? For an additional condition for example if the value is negative then insert one node which holds 1 (the same idea when we insert one node which holds 0 when e<3),how can we do that?

I tried something like that: 
1
2
3
4
5
6
 
	for (const auto& e : A)
{
		if (e >=3) insert(root, true);
                 if (e < 0) insert(root, true ?);
}


Thank you so much
lastchance (6980)
learner999 wrote:
The second question, maybe @lastchance can also answer it? For an additional condition for example if the value is negative then insert one node which holds 1 (the same idea when we insert one node which holds 0 when e<3),how can we do that?


(Note that there was an error in my previous code - which @seeplus duly copied! That code has been corrected)


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
 
#include <iostream>
#include <vector>
using namespace std;

struct node
{
   int data;
   node *left = 0, *right = 0;
};

void insert( node *n, bool add0, bool add1 )
{
   if ( n->left || n->right )         // NOT at bottom of tree, don't add branches
   {
      if ( n->left   ) insert( n->left , add0, add1 );
      if ( n->right  ) insert( n->right, add0, add1 );
   }
   else                               // at bottom of tree, so CAN add branches
   {
      if ( add0 ) n->left  = new node{ 0, 0, 0 };
      if ( add1 ) n->right = new node{ 1, 0, 0 };
   }
}

void output( node *n )
{
   if ( !n ) return;
   output( n->left );
   cout << n->data;
   output( n->right );
}

int main()
{
   vector<int> A = { 6, 4, 1, -2 };
   node *root = new node{ 0, 0, 0 };
   for ( int e : A ) insert( root, e >= 0, e < 0 || e >= 3 );  // add 0 if e is positive or zero
                                                               // add 1 if e is negative or >= 3
   output( root );
}


010001100101011


root                           0
                              / \
                             /   \
                            /     \
                           /       \
                          /         \
                         /           \
                        /             \
                       /               \
                      /                 \
check 6              0                   1
                    / \                 / \
                   /   \               /   \
                  /     \             /     \
                 /       \           /       \
check 4         0         1         0         1
               /         /         /         /
              /         /         /         /
check 1      0         0         0         0
              \         \         \         \
check -2       1         1         1         1
          
          ===========================================
             0 10    0 0 11    0 0 10    1 0 11

Last edited on
seeplus (6591)
one more question to @seeplus and I would be very happy if you can answer. In your solution, the point I can not understand how it decides it will make two branches 0 and 1 or just 0. For example the first value in the array is 6 which corresponds 1 in terms of boolean , is not it How does it insert the other branch which holds 0?


Looking at my code and @lastchanc's, it seems that we are doing it very similar.

There's two distinct conditions which are not related to each other. In my code L13-16 and L18-21. As you're said previously that this is as expected then the logic is OK.

Taking 6.
L13 is false so insert left new node 0.
L18 is false. L20 is true so insert right new node 1
learner999 (102)
Thank you so much @seeplus, in your code, I can not understand that part exactly, since 6>3 it should be true and we should add 1 . However, you explain the other way. I could not understand why L13 is false ? And how can I modify your code for the additional condition as lastchance does , how to add single node holding 1 when the value is negative?Thank you so much

Thank you so much @lastchance. When I iplement your code , I receive the following error:

main.cpp: In function ‘void insert(node*, bool, bool)’:
main.cpp:20:48: error: no matching function for call to ‘node::node()’
20 | if ( add0 ) n->left = new node{ 0, 0, 0 };

How can I fix it ?
Thank you so much
Last edited on
lastchance (6980)
learner999 wrote:
When I iplement your code , I receive the following error:
main.cpp: In function ‘void insert(node*, bool, bool)’:
main.cpp:20:48: error: no matching function for call to ‘node::node()’
20 | if ( add0 ) n->left = new node{ 0, 0, 0 };
How can I fix it ?


@learner999,
If you aren't prepared to upgrade your compiler to at least C++14 then you will have to either write a formal constructor for node (which is over-the-top for plain old data) or stop initialising the pointers within node (which would have abbreviated the initialisation quite usefully).

Try this one - it works in C++11. But I much prefer the other one.

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
 
#include <iostream>
#include <vector>
using namespace std;

struct node
{
   int data;
   node *left, *right;
};

void insert( node *n, bool add0, bool add1 )
{
   if ( n->left || n->right )         // NOT at bottom of tree, don't add branches
   {
      if ( n->left   ) insert( n->left , add0, add1 );
      if ( n->right  ) insert( n->right, add0, add1 );
   }
   else                               // at bottom of tree, so CAN add branches
   {
      if ( add0 ) n->left  = new node{ 0, 0, 0 };
      if ( add1 ) n->right = new node{ 1, 0, 0 };
   }
}

void output( node *n )
{
   if ( !n ) return;
   output( n->left );
   cout << n->data;
   output( n->right );
}

int main()
{
   vector<int> A = { 6, 4, 1, -2 };
   node *root = new node{ 0, 0, 0 };
   for ( int e : A ) insert( root, e >= 0, e < 0 || e >= 3 );  // add 0 if e is positive or zero
                                                               // add 1 if e is negative or >= 3
   output( root );
}


Personally, I think you will have a better C++ experience if you upgrade your compiler. C++14 didn't change much of the standard, but it did tidy up a few ragged ends. And now there is C++17 and (to some extent) C++20.

Last edited on
learner999 (102)
Thank you so much @lastchance for all your helps. I understood it better now
Topic archived. No new replies allowed.