Reputation: 31
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