How to Implement rotateLeft rotateRight in tree based on array?

I'm trying to implement a binary tree using an array. It means that the following tree

    1
   / \
  2   3
 / \ / \
4  5 6  7

would be as the array below: [1, 2, 3, 4, 5, 6, 7] So it means that the left is on index * 2 + 1, and the right is on index * 2 + 2;

I want to implement basic rotateLeft and rotateRight algorithms to binary tree. but working only with indexes, not references. Idk how to update the array correctly, because there's the problem:

Using basic algorithm as:

public TreeNode RotateLeft(TreeNode root)
{
    if (root == null || root.Right == null)
        return root;

    TreeNode newRoot = root.Right;
    root.Right = newRoot.Left;
    newRoot.Left = root;

    return newRoot;
}

remade with indexes it wouldn't working, because all the childs of the 'next level' wouldn't be updated, we need some approach to update it...😩

I mean we had:

[ 1, 4, 2, 5, 6, null, 3, null, null, null, null, null, null, 10, 20 ]

    1
   / \
  4   2
 / \   \
5  6   3
      / \
     10 20

After the rotateLeft with node that has value 2 means index 2 we should have:

[ 2, 1, 3, 4, null, 10, 20, 5, 6, null, null, null, null, null, null ]

     2
    / \
   1   3
  /   / \
 4   10 20
/ \ 
5  6 

I have no idea how to implement it. I think there should be recursive approach (but I'm NOT sure) because while trying do it iterative, i've got a lot of problems...

Idk how to explain it more clearly. THX a lot, if you've read it...

Upvotes: 1

Views: 30

Answers (0)

Related Questions