How to filter the subnodes of a tree using recursion in angular2

--**app.component.ts**
import { Component,OnInit } from '@angular/core';
import { Observable } from 'rxjs/Observable';
import { Subject } from 'rxjs/Subject';


@Component({
  selector: 'my-app',
  templateUrl:'./app.component.html'
})
export class AppComponent implements OnInit {
  Tree: any;
  private searchText$ = new Subject<string>();
  ngOnInit() {
    this.Tree = this.myTree;
  }

  myTree  = [
    { name: "parent1", subnodes: [{ name: "parent1_child1", subnodes: [{ name: "parent_child1_child1", subnodes: [] }] },{ name: 'parent1_child2', subnodes: [] }]  },
      {
          name: "secondparent2",
          subnodes: [
            { name: "secondparent2_child1", subnodes: [] }
          ]
      },
        {
          name: "thirdparent3",
          subnodes: [
              {
              name: "Chandigarh3",
                  subnodes: [
                    { name: "parent3_child1_child1", subnodes: [] }
                  ]
              }
          ]
      }
  ];

  filter(name: string):any {

    this.Tree = this.myTree.filter(data => data.name.match(name) || (data.subnodes.filter(subnode => (subnode.name.match(name))).length > 0) ? true:false);

  }

  search(input: string, data: any): boolean {
   let output= data.subnodes.filter(subdata => (subdata.name.match(name)))
   if (output != undefined && output.length > 0) {
     return true;
   }
   else {
     return false;
   }

    }

  }


--**app.component.html**
<h1>Tree as UL</h1>
<tree-view [treeData]="Tree"></tree-view>
<input   type="text"  (keyup)="filter($event.target.value)"  />

I am able to filter first parent nodes and corresponding subnodes but after that how to filter subnodes?
I have written search function so i can invoke search method from filter method by passing the input and tree , I want to use search method recursively

saving data of on-line edited D3.js tree

Hi I am Javascript newbie, I forked the code to create an editable D3.js tree visualisation, I would like to know how I can add the possibility to save the tree structure, for example as JSON file, after it has been edited on-line.

code on gist: https://gist.github.com/petergpython/d7c82ea9bd9c7c1bc61c6b3874cc0348

code and tree on bl.ocks.org: https://bl.ocks.org/petergpython/d7c82ea9bd9c7c1bc61c6b3874cc0348

thanks for any help or pointing out the right direction

Node removal in a BST java

As an assignement I have to implement my own version of a Binary search tree.
After the code finds the node, that shall replace the node which are to be removed. The node being copied to the one to be removeds place, still remains in the bottom of the tree after the method is over.

The logic seems to be working fine, the problem is the actual deletion.

                get(key).address.address = nodeRemove.address.address;
                get(key).key = nodeRemove.key;
                nodeRemove = null;
                return true;

After i have set nodeRemove to null, the reference and object is still there.

package binarysearchtree;

public class Node 

  int key;
  String address;
  Node rightChild;
  Node leftChild;

  Node(int key, Address address){
    this.key = key;
    this.address = address;
  }

}

This is my remove method(s)

public boolean remove(Integer key) {
    return remove(key, get(key));
}

private boolean remove(Integer key, Node nodeRemove) {
    if (root == null) {
        return false;
    }


    if (contains(nodeRemove.key)) {

        if (nodeRemove.key <= key) {

            //Searching for largest of smallest
            if (nodeRemove.key == key && nodeRemove.leftChild != null) {
                remove(key, nodeRemove.leftChild);

            } else if (nodeRemove.key < key && nodeRemove.rightChild == null) {

                get(key).address = nodeRemove.address;
                get(key).key = nodeRemove.key;
                nodeRemove = null;
                return true;
            }
        }
        if (nodeRemove.key >= key) {

            if (nodeRemove.key == key && nodeRemove.rightChild != null) {
                remove(key, nodeRemove.rightChild);

            } else if (nodeRemove.key > key && nodeRemove.leftChild == null) {
                get(key).address = nodeRemove.address;
                get(key).key = nodeRemove.key;
                nodeRemove = null;
                return true;
            }
        }
    }
    return false;
}

Java generic tree traversal with node filtering

I have a generic tree structure.
I need an algorithm to traverse it, and remove some leafs if they are not contained in a given list. If all the leafs are removed from a subtree, then remove the whole subtree too.

Example tree:

         0
       / |  \
      1  2   3
    /  \ |  / \
   4   5 6  7  8

Leafs to keep: {4, 6}

Result tree:

         0
       / | 
      1  2 
    /    | 
   4     6  

The input data structure is contained in a HashMap where the key is the parent id of the nodes, and the value is a List of the Nodes directly under the parent (but not recursively all children). The parent id of the root node is empty string.

Map<String, List<Node>> nodes;

class Node {
    private String id;
    //other members
    //getters, setters
}

I suppose, some kind of recursive DFS traversal algorithm should work, but I couldn’t find it out, how.

Java generic tree traversal with node filtering

I have a generic tree structure.
I need an algorithm to traverse it, and remove some leafs if they are not contained in a given list. If all the leafs are removed from a subtree, then remove the whole subtree too.

Example tree:

         0
       / |  \
      1  2   3
    /  \ |  / \
   4   5 6  7  8

Leafs to keep: {4, 6}

Result tree:

         0
       / | 
      1  2 
    /    | 
   4     6  

The input data structure is contained in a HashMap where the key is the parent id of the nodes, and the value is a List of the Nodes directly under the parent (but not recursively all children). The parent id of the root node is empty string.

Map<String, List<Node>> nodes;

class Node {
    private String id;
    //other members
    //getters, setters
}

I suppose, some kind of recursive DFS traversal algorithm should work, but I couldn’t find it out, how.

I got segmentation fault when deleting a node…can anyone spot the mistake?

sorry, if this question is too basic but I am trying to delete a node in binary search tree in c++, the function works fine for the root, but when I delete the leaf node it gets me segmentation fault. I’ve checked that the problem is in the statement where I am deleting the node. Here’s the code. Thanks for the help.

here’s the link for source code : https://codeshare.io/adpg7K

~Node()
{
    if (left != NULL)
        delete left;
    if (right != NULL)
        delete right;
}

//if it is root
//closest to the middle value of the string so as to make a balanced tree
if (root->word == wordArg) {
    Node *leftchild, *rightchild, *tmp, *tmpdel;
    leftchild = root->left;
    rightchild = root->right;
    tmpdel = root;
    tmpdel->left=NULL;
    tmpdel->right=NULL;
    delete tmpdel;
    root = rightchild;
    tmp = root;
    while (tmp != NULL){
        if (leftchild->word < tmp->word) {
            if (tmp->left == NULL) {
                tmp->left = leftchild;
                return;
            }
            else {
                tmp = tmp->left;
                return;
            }
        }
        else {
            if (tmp->right == NULL) {
                tmp->right = leftchild;
            }
            else {
                tmp = tmp->right;
            }
        }
    }
    return;
}

Node *parent, *tmp, *leftc;
tmp = root;
//if it is leaf set parents left or right field to null

//if it is middle
while (tmp != NULL) {

    if (tmp->word == wordArg) {
        //found

        if (tmp->word < parent->word) {

            parent->left = tmp->right;
        }
        else {
            parent->right = tmp->right;
        }
        leftc = tmp->left;
        tmp->left=NULL;
        tmp->right=NULL;
        delete tmp;

        if (parent->word < wordArg) {
            tmp = parent->left;
        }
        else {
            tmp = parent->right;
        }

        while (tmp != NULL) {
            if (leftc->word < tmp->word) {
                if (tmp->left == NULL) {
                    tmp->left = leftc;
                }
                else {
                    tmp = tmp->left;
                }
            }
            else {
                if (tmp->right == NULL) {
                    tmp->right = leftc;
                }
                else {
                    tmp = tmp->right;
                }
            }
        }
        return;
    }
    else if (wordArg < tmp->word) {
        parent = tmp;
        tmp = tmp->left;
    }
    else {
        parent = tmp;
        tmp = tmp->right;
    }


}
cout << endl
     << "Word not found!";

Find minimum Characters required from the subtreee

You are given a rooted tree with N nodes. Each node contains a lowercase English letter. Node with label 1 is the root.
There are Q questions of the form,
X S: Here X is the root of subtree and S is a string.

For each question, let T be the string built using all the characters in the nodes of subtree with root X (each subtree node character comes exactly once) .
For each question, print minimum number of characters to be added to T , so that the we can build S using some characters of string T
(each character of string T can be used at most once).

Input Format:

The first line of input consists of two space separated integers
N and Q that are number of nodes in the tree and number of questions respectively.
Next line will contain
N space separated lowercase English letters, where ith letter will be the letter stored in node with label i .
Each of the next N?1 lines contains two space separated integers
u and v that denote there is an edge between nodes with labels u and v
Next Q lines follow. Each line will contain an integer
X that denotes the node label and a string
S separated by a single space.

Output Format:

For each query, print the required answer in a new line.

Input Constraints
2?N?105
1?Q?105
1?u,v?N;u!=v
1?X?N

All characters in nodes and string are lowercase English letters.
Sum of lengths of strings in all the questions is at most 10^6

Sample Input

8 3

o v s l v p d i

1 3

8 3

4 8

6 1

5 3

7 6

2 3

7 ifwrxl

4 eyljywnm

3 llvse

Sample Output:

6

7

2

Explanation

Query 1- Character in the subtree with root 7 is d, we need 6
characters(i,f,w,r,x,l) to make S=(ifwrxl).

Query 2- Character in the subtree with root 4 is l, we need 7 characters(e,y,j,y,w,n,m) to make S=(eyljywnm).

Query 3- Characters in the subtree with root 3 are (v,s,i,l), we need 2 characters(l,e) to make S=(llvse).

Tree depth: car/cdr contract violation

I’m using racket to return the depth of a given tree. Here’s the current code:

(define (depth tree)
   (cond
      [(empty? tree) 0]
      [else
       (+ 1 (max (depth (cadr tree))
                 (depth (caddr tree))))]))

I haven’t been able to test it though because I always get a run-time error about violating the contract of car and cdr. To be specific, when I try

(depth '(1 2 3))

which should return 1, I encounter:

length: contract violation
  expected: list?
  given: 2

No matter what I do, the problem stays, and I’m not allowed to change the test case to fix the problem. I’m sure it’s simple, but could someone please help me understand?

(I’ve looked at other posts; some discuss the algorithm of depth but I’m asking specifically about the car/cdr contract violation as presented here.)

How to make binary tree from array in javascript?

I have an array var array = [8,10,12,5,3,6];

Logic

  1. First node would be root node.
  2. If new node value is less or equal =< than parent node, It would be left node of parent node
  3. If new node value is greater > than parent node, It would be right node of parent node

And I am trying to achieve output like below object:

{
   value:8,
   left:{
      value:5,
      left:{ value:3 },
      right:{value:6}
   },
   right:{
      value:10,
      right:{value:12}
   }
}

Which would be in image like this

enter image description here

I tried below code:

var arr = [8,10,12,5,3,6];
var root = arr[0];
var rv = {};
for (var i = 0; i < arr.length; i++){
    if(arr[i] < root){
    rv.left = arr[i];
  }else{
    rv.right = arr[i];
  }
}
console.log(rv);

Please help me to solve this.

What is wrong with my CountHeight function for binary trees (Javascript)

var CountHeight = function(root){
    if(root == null){
       console.log("NULL!")
       return 0;
    }

    leftheight = CountHeight(root.left);
    rightheight = CountHeight(root.right);
    if (leftheight > rightheight){
        return leftheight + 1;
    } else if(rightheight > leftheight){
        return rightheight + 1;
    } else if(rightheight == leftheight){
        return leftheight + 1;
    }

}

Each root has a left and right value that points to another tree.

I tried to test out this function by plugging in a tree (I know the function takes a parameter called root but I’m basically passing a tree into it). The tree I passed on looked something like this:

(root)10: (leftofroot)left: 4 - left: null right: 8
(rightofroot)right: 15 - left: null right: null

If you cant follow the above diagram, I’m basically adding the following nodes ot my tree: 10, 4, 15, 8

Ok, so when I passed my tree into the function, I got the value of 2, but clearly my tree has a height of 3. The node 8 being the only node with that has a depth of 3.

So can someone tell me what’s going wrong with my function?

PS: I’m struggling, if my question is too confusing, can someone give me another function that finds the height of a tree when I pass a tree into it.

Thanks!

var testBST = new BST();
testBST.addNode(10);
testBST.addNode(4);
testBST.addNode(15);
testBST.addNode(8);

console.log(testBST);
console.log(CountHeight(testBST));