Outline of a Binary Tree
Updated
Problem statement
You are given the root of a binary tree. Return the values on the tree's outline: start at the root, go down the left side, go along the bottom from left to right, and come back up the right side.
The outline is these four parts joined in this order. No node is listed twice.
- The root.
- The left side, from top to bottom. It starts at the root's left child; if the root has no left child, the left side is empty. From a node on the left side, the next node is its left child if it has one, and otherwise its right child. The left side stops before it reaches a leaf.
- Every leaf, from left to right. A leaf is a node with no children. The root is never counted as a leaf.
- The right side, from bottom to top. It is the mirror of the left side: it starts at the root's right child, the next node is the right child if there is one and otherwise the left child, and it stops before a leaf. List these nodes from the lowest one up.
Function
treeOutline(root: TreeNode) → int[]Examples
Example 1
root = [1,2,3,4,5,6,7,null,null,8,9]return = [1,2,4,8,9,6,7,3]The root is 1. The left side is just 2: its left child 4 is a leaf, so the left side stops there. The leaves from left to right are 4, 8, 9, 6 and 7. The right side is just 3, because its right child 7 is a leaf. Joined together: [1, 2, 4, 8, 9, 6, 7, 3]. Node 5 is inside the tree, so it is not on the outline.
Example 2
root = [1,null,2,3,4]return = [1,3,4,2]The root has no left child, so the left side is empty. The leaves are 3 and 4. The right side is 2: its right child 4 is a leaf, so the side stops there. The answer is [1, 3, 4, 2].
Example 3
root = [5,3,null,null,4,6]return = [5,3,4,6]The left side starts at 3. Node 3 has no left child, so the side goes on to its right child, 4. The next node, 6, is a leaf, so the left side is 3, 4. The only leaf is 6. The root has no right child, so the right side is empty. The answer is [5, 3, 4, 6].
Example 4
root = [7]return = [7]The tree is a single node. The root is never counted as a leaf, so it is listed once: [7].
Constraints
- The number of nodes is between
1and10^4. -1000 <= node.val <= 1000- Node values do not have to be different.
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
- Odd Numbers Up and BackPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
- Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
- Delete a Filesystem TreeDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
- Turn a BST Into a Sorted Doubly Linked ListAdobe · PHONE SCREENAdobe interview questions
- Kth Smallest Value in a BSTExpedia · PHONE SCREEN · ONSITE INTERVIEWExpedia interview questions
- Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
- Binary Tree Preorder TraversalMorgan Stanley · PHONE SCREENMorgan Stanley interview questions
- Binary Tree Inorder TraversalBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Recover a Tree from Preorder Depth EncodingSuperhuman · PHONE SCREENSuperhuman interview questions
- Filesystem Entity Total SizeGoogle · ONSITE INTERVIEWGoogle interview questions