2

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:

  • How to update all the childs.

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...

Improve this question
11
  • Language-agnostic related post. Commented Mar 10 at 17:36
  • I'm assuming that by rotateLeft and rotateRight you are referring the usual Tree rotation operations? Commented Mar 10 at 17:39
  • Wyck, yeah, you're right Commented Mar 10 at 17:47
  • 1
    I think you're on the right track...ish. Stick to the basics (Identify >> Swap >> Update). You essentially need to update all the affected children, and keep correct parent-child relationships. Make sure you check if you indices are within bounds, and that the children exist. Commented Mar 10 at 18:41
  • 1
    It really is not worth doing that: it destroys the efficiency-benefit that rotations are intended for. Commented Mar 10 at 21:18
Related questions
12225
How can I remove a specific item from an array in JavaScript?
5801
Loop (for each) over an array in JavaScript
5004
How do I check if an array includes a value in JavaScript?
Load 7 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.