Member Avatar for sivaslieko++

hi,
I have a problem with BST. For example after the insertions of below numbers,
23 1 45 2 3 5 52 234 31

The output should be like this way:

23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

I have no problem in insertion but
I could not developed any method to output in this format:((
Is there anyone who can help me :sad:

  • 4 Contributors
  • 6 Replies
  • 121 Views
  • 3 Years Discussion Span
  • Latest Post Latest Post by lotrsimp12345

Dani AI

Generated

The output you want is just a level-order (breadth-first) print but with two rules: each parent is shown as a pair "L,R" (comma between siblings) and missing children print as -, with parent-pairs separated by |. was right to point at level-order; shows a per-level recursion approach but that version does not keep null placeholders so it won't produce the - slots you need. The simplest, robust way is an iterative BFS that enqueues real child pointers and also enqueues nullptr for missing children so positional structure is preserved. Stop when the next level would be all nullptr to avoid printing infinite trailing - lines.

Example C++ sketch (keeps nullptrs in the queue, prints one line per "children-of-the-current-level"):

struct Node { int key; Node* left; Node* right; };

void printWithNulls(Node* root) {
    if (!root) { printf("-\n"); return; }
    printf("%d\n", root->key);              // first line: root alone
    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int sz = q.size();
        bool anyNonNullChild = false;
        std::string line;

        for (int i = 0; i < sz; ++i) {
            Node* parent = q.front(); q.pop();
            Node* L = parent ? parent->left  : nullptr;
            Node* R = parent ? parent->right : nullptr;

            line += (L ? std::to_string(L->key) : "-");
            line += ",";
            line += (R ? std::to_string(R->key) : "-");

            if (i + 1 < sz) line += " | ";

            if (L) anyNonNullChild = true;
            if (R) anyNonNullChild = true;

            q.push(L);
            q.push(R);
        }

        if (!anyNonNullChild) break;   // stop before printing an all-'-' level
        printf("%s\n", line.c_str());
    }
}

Tips and cautions:

  • This prints exactly the format you showed (root on first line, then parent pairs).
  • For very tall trees you may want to compute a height limit and stop earlier; keeping nulls doubles queue size each level (exponential growth), so large depth produces huge output.
  • If using a recursive per-level routine (like ), you must explicitly treat null nodes as nodes that still generate - placeholders for their children or use a fixed depth to avoid missing positions.
  • : inorder is for sorted output and won’t produce this positional representation.

Recommended Answers

All 6 Replies

Member Avatar for Member #46692

Hint:

You need a Level order traversal algo. To implement a level-order traversal, you need a first-in first-out queue--not a stack.

You might also need to find out the maximum height of your tree.

No idea if that is actually correct but it seems logical ???

Member Avatar for Member #46692

You could also look at the algorithm of REINGOLD AND TILFORD, maybe?

That might be beyond the scope of what you're trying to do though.;)

Member Avatar for sivaslieko++

Hi,
actually I implemented Level order traversal successfull but I could not print like this way :

23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

How can I insert "-" for null subtrees properly?
Thaks..

Member Avatar for Member #46692

Erm, this is just pure guesswork (and could be completely wrong) but if you encounter a null thingy couldn't you just print a -, ?

visitlevel(S)
  T = Set()
  for each node in S   
    print node.Value
    if (node->left != null)
       T.insert(node->left)
    if (node->right != null)
       T.insert(node->right)
  if ( T.empty() != true)
    visitlevel(T)

visit(root)
  S = Set()
  S.insert(root)
  visitlevel(S)
if node is empty Then
   print "-,"
EndIf
23 1 45 2 3 5 52 234 31

And the tree:

23
              /    \
             1      45
              \     / \
               2   31  52
                \       \
                 3      234
                  \
                   5
Member Avatar for mkt193

i need to understand how this function work

void BinarySearchTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}
Edited by WaltP because: COLOR tags are not CODE tags. Please read the information on posting correctly all over this site.
Member Avatar for lotrsimp12345 
template <class KT, class DT>
void my_bst<KT,DT>::printLevelOrderAux(my_bst_node<KT,DT>* t, int level)
{
	if(t) 
	{
		if(level == 1) 
		{
			printf(" %d ", t->key);
		}
		else if (level > 1) 
		{
			printLevelOrderAux(t->left, level-1);
			printLevelOrderAux(t->right, level-1);
		}
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::printLevelOrder(my_bst_node<KT,DT>* t,int height) 
{
	int i;

	for(i = 1; i <=height; i++) 
	{
		printLevelOrderAux(t, i);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::show(int height)
{
	printLevelOrder(root,height);
}
Edited by lotrsimp12345 because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.