1

So, the idea is that I have an arbitrary binary tree (with no rules regarding height balancing or ordering) and I want to insert a number 'x' at an index 'i' in the inorder traversal of the binary tree (and shift all the subsequent nodes one step to the right). This could be trivially solved in O(n), but I want to find a solution in O(logn). I'm fairly confident I'll need an AVL tree to do this. It's been almost a week and I still haven't made any progress, so I'm turning to the StackOverflow community to see if they can nudge me in the right direction.

EDIT: Here's the rough O(n) implementation if it helps. It's pretty repulsive. You can get away with just maintaining the inorder traversal if you want to do it in O(n). Here num is the number we want to insert into the binary tree, index is the index we want to insert it at, and inorder is the array that maintains the inorder traversal of the binary tree.

insert(num, index, inorder[])
    if (index >= inorder.size())
        1. Keep adding '-1' to the end of the inorder array until its size is 'index'
        2. Add 'num' to the end of the array
    else if (inorder[index] == -1)
        inorder[index] = num
    else
        1. Right shift the inorder array from inorder[index] onwards
        2. inorder[index] = num

EDIT: Also, this is actually part of a competitive programming question that someone sent me. The end goal is to be able to return any element given its index in the inorder traversal of the tree. I feel like the solution is something out-of-the-box and maybe doesn't even require building a tree at all.

Zantorym
  • 99
  • 1
  • 7
  • 1
    Professional programmers will tell you to not implement your own tree. There are many explanations and examples of red-black tree and AVL trees available online, and might be a better starting point than here. There is no guarantee that your search for the *i*-th element will be in O(lg n) unless the tree itself offers it as a feature. – jxh Sep 07 '21 at 01:34
  • 4
    Order-statistic trees are a thing and the answer to these questions. – Davis Herring Sep 07 '21 at 03:27
  • @DavisHerring Just checked them out and you might be right. Gonna try to figure out a solution using them. Thank you! – Zantorym Sep 07 '21 at 03:40
  • I just posted an answer the other day [here](https://stackoverflow.com/a/68942111/2034787). – גלעד ברקן Sep 07 '21 at 09:47
  • @גלעדברקן I'm not sure that's what I was looking for – Zantorym Sep 09 '21 at 06:59
  • @DavisHerring I was able to figure out an O(h) solution using the knowledge I gained from order-statistic trees. In my solution, each node keeps track of the size of its subtree. Essentially, if the index I want to insert a node at is less than or equal to the size of the left subtree, I insert the node there. Otherwise, I insert the node in the right subtree. My issue here is that there's no height balancing, so I'm still not at O(logn). (1/2) – Zantorym Sep 09 '21 at 07:00
  • All the implementations of height balancing I've seen assume that they're working on a BST and use the values of the nodes in conjunction with the value of the height difference of the left and right subtrees to determine which type of rotation to use when balancing. In my implmentaion, I'd only have the height difference and the number of nodes in each subtree to work with. (2/2) – Zantorym Sep 09 '21 at 07:03
  • Well, absent a sort order, balancing a tree isn't well defined: what does it mean if this node is now the parent of that one? – Davis Herring Sep 09 '21 at 07:18

0 Answers0