# Posts published in “Tree”

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Binary tree [2,1,3], return true.

Example 2:

Binary tree [1,2,3], return false.

# Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

# Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

# Related Problem

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Idea:

Binary format

serialized size: 4*n bytes, n is the number of nodes in the BST.

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++

Related Problems

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

Return 6.

Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

# Solution: Recursion

## Python3

Related Problems:

Problem:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Idea:

Recursion

Solution1:

C++

Solution 2: passed 101/106 TLE

C++ / Floyd-Warshall

Solution 3:

Simulate recursion with a stack. We also need to track the return value of each node.

Python

C++

Related Problems:

https://leetcode.com/problems/longest-univalue-path/description/

Problem:

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

              5
/ \
4   5
/ \   \
1   1   5


Output:

2


Example 2:

Input:

              1
/ \
4   5
/ \   \
4   4   5


Output:

2


Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

Idea:

DFS

# Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

# Related Problems

Mission News Theme by Compete Themes.