Implement range-sum tree and sort merged lists

Q: Implement range-sum tree and sort merged lists

This question evaluates proficiency in data structures and algorithms, focusing on tree traversal and range-query reasoning (including how binary search tree invariants affect strategy) and on in-place merging and pointer manipulation for singly linked lists.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a binary tree whose nodes store integer values, and two integers low and high defining an inclusive range [low, high], write a function that returns the sum of all node values within the range. Implement the solution in C++, explain your approach, and analyze its time and space complexity. Discuss how your strategy would change if the input were guaranteed to be a binary search tree and why.
Given two singly linked lists of integers (not necessarily sorted), merge them into a single singly linked list whose nodes are in nondecreasing order. Reuse the existing nodes (avoid allocating new value nodes except constant-overhead helpers). Implement the solution in C++, explain the algorithm, and analyze time and space complexity. If the input lists are already sorted, describe a linear-time alternative and its complexity.

Implement range-sum tree and sort merged lists

Overview

Comments (0)