Traversal/Preorder

Problem Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked. Design a binary tree node class with the following methods: is_locked, which returns whether the node is locked lock, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true. unlock, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true. You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree. ...

Problem Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. Examples Example 1: 3 / \ 9 20 / \ 15 7 ...

Sum of Distances in Tree Problem Problem There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes. ...

Problem Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. graph TD; A(3) --- B(5) & C(1) B --- D(6) & E(2) E --- F(7) & G(4) C --- H(9) & I(8) style D fill:#4682B4,stroke:#333,stroke-width:2px style F fill:#4682B4,stroke:#333,stroke-width:2px style G fill:#4682B4,stroke:#333,stroke-width:2px style H fill:#4682B4,stroke:#333,stroke-width:2px style I fill:#4682B4,stroke:#333,stroke-width:2px ...

Problem Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. Examples Example 1: Input: nums = [1, 2, 3, 4, 5, 6] Output: [3,2,5,1,null,4,6] Explanation: [4,2,5,1,3,null,6] is also accepted. ...

Maximum Depth of Binary Tree Problem Given a binary tree, find its maximum depth. Definition A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. The number of nodes along the longest path from the root node down to the farthest leaf node. Depth of root node is 0. Example Example 1 ...

Problem Given the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. Examples Example 1: ...