CODEWITHSUNDEEP
javadata-structurestree2-3-tree
Blagch
Blagch

Reputation: 95

How to print 2-3 tree from min to max?

I don't know how to approach the algorithm. I was thinking something like that:

TreeNode n = root;
while(n.first.first!=0){ 
    n=n.first;
} // finding the leftMost parent
//printing the first child key, then first num of parent, then second child.. and so on

Does somebody have better idea?

Upvotes: 0

Views: 2688

Answers (1)

Jakub Ch.
Jakub Ch.

Reputation: 3717

According to 2-3 tree definition, you could meet 3 types of nodes:

  • internal node with 2 children and 1 value
  • internal node with 3 children and 2 value
  • leaf with no children and 1 or 2 values

Having that information you could use a recursive method walking through nodes, starting from root node. If it meet leaf node it simply print values. In other cases the method have to call itself for the most left node (jump to left node), then print first value, then jump to next node and so one. After that the method is ending so the whole algorithm is ending (if actual node is a root node) or jump back to parent node (if actual node is an internal, children node)

Here is the pseudocode. I left the actual implementation for yourself. Study that and make sure you understand the method's flow (you could usue debugger and track the actual parameters)

/* you start algorithm by calling recursivePrint(root) */

void recursivePrint(node){

    if (node is a leaf){

        /* Here print node's value/values */

    } else if (node has 2 children){

        recursivePrint(node.leftChild);
        /* Here print node's value */
        recursivePrint(node.rightChild);

    } else if (node has 3 children)

        recursivePrint(node.leftChild);
        /* Here print node's left value */
        recursivePrint(node.middleChild);
        /* Here print node's right value */
        recursivePrint(node.rightChild)

    }

    /* Shouldn't be other cases in 2-3 trees */
}

Upvotes: 2

Related Questions