# Questions tagged [trees]

Questions about a special kind of graphs, namely connected and cycle-free ones.

741 questions
Filter by
Sorted by
Tagged with
20 views

### Rebalance the following AVL tree after inserting G. You need to show the middle step if it happens. Briefly explain the operations

I recently learned AVL Trees but I still lack a complete understanding of the concept. I understand that an AVL tree is a Binary search tree that checks for the height of the tree, but I still don't ...
26 views

### How is red-black tree insertion more effective than avl tree insertion

I'm having trouble understanding why RB tree insertion is called more effective in all sources. It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
53 views

### Why recording non-existent children in the pre-order traversal will differentiate different binary trees?

I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
119 views

### Print all nodes which are the endpoint of the diameter of a tree

Given a tree with n nodes, Print all nodes which are the endpoint of the diameter. 1<= n <=100000. E.g. For Above tree answer would be A,B,F,G I tried the O(n2) approach (Running Dfs from each ...
26 views

### Removing and adding edges from spanning tree

Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
96 views

### Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question : Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
27 views

### Shortest path in a tree

Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
26 views

### What is the name of a sequence structure where writes in the same area are faster?

I recall reading about a data structure for sequences where writes in the same area are faster due to some kind of caching or structure manipulation. What are some structures that do this? I know a ...
21 views

### using TRIE for strings?

I saw the following question online: Init - Initlize data structure in O(1). Insert(s) - Add string s to your Data Structure in ...
34 views

### How to trasnform search tree into AVL tree with constant memory and in linear time? [closed]

How to transform search tree into AVL tree with constant memory and in linear time ?
36 views

### Query sum of values between lo and hi for a stream of numbers

Suppose you have a stream of incoming numbers that you're storing and at any given instant in time, you want to query the sum of values between a given lo and ...
24 views

### Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....