Convert a sorted linked list to a balanced BST

Asked atApple
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below
0
Stuck? Show a way to structure it+
  1. 01Count list length.
  2. 02Recursively build the left subtree for half the nodes.
  3. 03Use the current list node as root.
  4. 04Advance the shared list pointer.
  5. 05Build the right subtree from the remaining nodes.

Reference answer

Then expect these follow-ups

  • What is the complexity of repeated slow/fast midpoint splitting?

    Tests: complexity analysis

  • Why does inorder construction preserve BST order?

    Tests: correctness reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.
  • Software Engineer - Applied AI

    Redwood Software · Hyderabad, Telangana, India

  • Software Engineer - UCD

    Texas Instruments · India

  • Staff Software Engineer

    Inspectorio · Ho Chi Minh, Vietnam

Or practice this question first

Next question

Convert a sorted linked list to a balanced BST