0

So I have a binary tree implementation which looks like this

struct node {
    struct node *left;
    struct node *right;
};

(the actual implementation is slightly more complex as there is additional data being stored as this is for a boolean algebra simplifier, but for the purpose of getting my point across I'll keep it simple)

basically I recieve a tree and I need to transform it so that it is completely left leaning

for example

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

needs to become

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

I understand the concept of tree rotations but I don't really know how to use them (or any other algorithm for that matter) to make the tree lean completely left like the diagram above

If anyone could point me in the direction of a algorithm or other resource to do this I would be very appreciative

dangee1705
  • 3,445
  • 1
  • 21
  • 40
  • 2
    You can completely deconstruct the tree into a sorted array (in-order) and then compose a new one. How? Try it on paper. Divide the in-order array to odd and even positions and start inserting into a new tree - first one group then the other - in reverse order. – Eugene Sh. Sep 30 '19 at 20:06
  • Is there a way to do it recursively possibly? – dangee1705 Sep 30 '19 at 20:16
  • @dangee1705 Maybe not the answer you want, but yes. All loops can be expressed as recursions. – klutt Sep 30 '19 at 20:33
  • @dangee1705 And I don't wanna be that guy, but it was not exactly hard to find resources online. https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf – klutt Sep 30 '19 at 20:40
  • I would recommend redrawing the first tree. Draw it in a way so that all lines are equally long. The way it is drawn now, you "see" stuff that is impossible to use in code. For instance, you can see that b should drop down, just because the line between b and c are longer than the line between c and e. But this is not something you can use in your algorithm. At least not in a trivial way. – klutt Sep 30 '19 at 20:45
  • 1
    Another thing. When trying to make a recursive algorithm. Start with the case where you have three nodes. Draw all possible versions of binary trees with three nodes. You'll quickly realize that there's only one, so this is a good base case for the algorithm. (I'm making the assumption that a node has 0 or 2 children.) Then go to four nodes. Ups, there are no binary trees with four (actually, there are no bintrees with even number of) nodes, so go up to five. Now we're talking. There are two different bintrees, and one of them is left leaning. – klutt Sep 30 '19 at 21:22
  • 1
    So find an algorithm that takes a bintree with five nodes and make it left leaning. Then you step up to seven nodes. There are now six different trees. Figure out how to first fix a 3-node LL-subtree, and then how to make a 5-node LL-subtree and finaly fix a 7-node LL-subtree. Do this for all six trees by hand. When this is done, you probably have a working algorithm. – klutt Sep 30 '19 at 21:25
  • I am a bit confused by `d` and `g`. If it weren't for them, I would probably just rebuild the tree from H to O using an inorder traversal (LEFT->ROOT->RIGHT). – AugustinLopez Sep 30 '19 at 23:17

0 Answers0