JP Morgan Data Engineer Interview Questions (2026)

A Binary Search Tree (BST) can be converted into a skewed tree, essentially a sorted linked list, by performing an in-order traversal and strategically re-wiring the node pointers. This process leverages the inherent sorted property of a BST's in-order traversal to create a new structure where all nodes are linked sequentially, either in increasing (right-skewed) or decreasing (left-skewed) order. ### Mechanics and "Why" The core idea is to flatten the tree into a linear structure by modifying its `left` and `right` pointers during a traversal. * **Increasing Order (Right-Skewed):** 1. Perform an in-order traversal (left child -> current node -> right child). 2. Maintain a `prev` pointer, which tracks the last node processed in the desired order, and a `head` pointer for the start of the new skewed tree. 3. For each `current_node` visited: * Set `current_node.left = None` to eliminate its left child and ensure the tree skews to the right. * If `prev` exists, set `prev.right = current_node` to link the previous node to the current one. * If `head` is not yet set (i.e., this is the very first node processed), set `head = current_node`. * Update `prev = current_node`. * **Decreasing Order (Left-Skewed):** * This is achieved by performing a reverse in-order traversal (right child -> current node -> left child). * For each `current_node`, set `current_node.right = None` and link `prev.left = current_node`. This modification is performed **in-place**, meaning no new nodes are created; only existing pointers are reassigned. **Complexity:** * **Time Complexity:** O(N), as every node in the BST must be visited exactly once. * **Space Complexity:** O(H) for the recursion stack, where H is the height of the BST. In the worst case (a completely skewed BST), H can be N, leading to O(N) space. ### Example and Trade-offs Here's a Python example for converting a BST into an increasing (right-skewed) tree: ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def convert_bst_to_skewed(root): # Use a list to hold the 'prev' node and the 'head' of the new skewed list # so they can be modified by recursive calls. state = [None, None] # [prev_node, head_node] def _inorder_flatten(node): if not node: return _inorder_flatten(node.left) # Process current node if not state[1]: # If head is not set, this is the first node state[1] = node else: state[0].right = node # Link previous node to current node.left = None # Ensure left child is None for right-skewed state[0] = node # Update prev_node to current _inorder_flatten(node.right) _inorder_flatten(root) return state[1] # Return the new head of the skewed tree ``` **Trade-offs:** While efficient in time and space, this operation fundamentally changes the data structure. A BST offers logarithmic time complexity (O(log N)) for search, insertion, and deletion in a balanced tree. Converting it to a skewed tree (a linked list) degrades these operations to linear time complexity (O(N)), making it unsuitable for scenarios requiring efficient searching or balancing. ### In the interview, also mention… In the interview, also mention that while this specific transformation is rare in production data systems, understanding pointer manipulation and tree traversals is crucial for optimizing data structures like B-trees (used in databases like Snowflake for micro-partitions and indexing) or managing distributed data structures where node relationships are critical for performance and data integrity. This problem tests fundamental data structure manipulation skills.